1. 堆数据结构的定义
2. 堆的数组表示
3. 堆的调整函数
4. 堆排序实践

1.堆的简介

堆是计算机科学中的一种特别的树状数据结构。
若是满足以下特性，即可称为堆：给定堆中任意节点P和C，若P是C的母节点，那么P的值会小于等于C的值。若母节点的值恒小于等于子节点的值，此堆称为最小堆；反之称为最大堆。
堆始于J. W. J. Williams在1964年发表的堆排序，当时他提出了二叉堆树作为此算法的数据结构，堆在戴克斯特拉算法和带优先级队列中亦为重要的关键。

数据结构中的堆区别于内存分配的堆，我们说的用于排序的堆是一种表示元素集合的结构，堆是一种二叉树。

堆有两个决定性特性：元素顺序和树的形状

• 元素顺序：
  在堆中任何结点与其子结点的大小都遵守数值大小关系。
  A. 如果结点大于等于其所有子结点，也就是堆的根是所有元素中最大的，这种堆称为大根堆(大顶堆、最大堆)；
  B. 如果结点小于等于其所有子结点，也就是堆的根是所有元素中最小的，这种堆称为小根堆(小顶堆、最小堆)；
  C. 大根堆/小根堆只是约定了父结点和子结点的大小关系，但是并不约束子结点的相对大小和顺序；
  如图为小根堆结构：

• 树的形状：

堆这种二叉树最多在两层具有叶子结点，并且最底层的叶子结点靠左分布，该树种不存在空闲位置，也就是堆是个完全二叉树。上述的两种性质可以保证快捷找到最值，并且在插入和删除新元素时可以实现重新组织再次满足堆的性质。

2.堆的数组表示

堆中没有空闲位置并且数组是连续的，但是数组的下标是从0开始，为了统一，我们统一从1开始，也就是root结点的数组index=1，那么可以通过数组的index可以通过父结点找到左右子结点，也可以通过子结点找到父结点。数组的元素遍历就是堆的层次遍历的结果，因此数组存储的堆具备以下性质：

//数组下标范围i<=n && i>=1//根结点下标为1root_index = 1//层次遍历第i个结点的值等于数组第i个元素value(i) = array[i] //堆中第i个元素的左孩子下标i*2left_child_index(i) = i*2//堆中第i个元素的右孩子下标i*2+1right_child_index(i) = i*2+1//堆中第i个元素的父结点下标i/2parent(i) = i/2

堆和数组的对应关系如图：

3.堆的调整函数

堆调整的过程非常像数学归纳法的递推过程，看一下就知道。

敲黑板！以下两个函数对于掌握堆非常重要。

• siftup函数的原理

以小根堆为例，之前a[1...n-1]满足堆的特性，在数组a[n]插入新元素之后，就产生了两种情况：

A. 如果a[n]大于父结点那么a[1...n]仍然满足堆的特性，不需要调整；

B. 如果a[n]比它的父结点要小无法保证堆的特性，就需要进行调整；

循环过程：自底向上的调整过程就是新加入元素不断向上比较置换的过程，直到新结点的值大于其父结点，或者新结点成为根结点为止。

停止条件：siftup是一个不断向上循环比较置换的过程，理解循环的关键是循环停止的条件，从伪码中可以清晰地看到，siftup的伪码：

//siftup运行的前置条件heap(1,n-1) == True void siftup(n)      i = n      loop:          // 循环停止条件一          // 已经是根结点         if i == 1:              break;          p = i/2         // 循环停止条件二          // 调整结点大于等于在此位置的父结点         if a[p] <= a[i]               break;          swap(a[p],a[i])          // 继续向上循环         i = p

siftup调整过程演示

在尾部插入元素16的调整过程如图：