一、堆

堆是一种数据结构，通常通常所说的堆即二叉堆。二叉堆是一个数组，可以被看成一个完全二叉树，如下图所示：

他在数组中的表现形式为：

通过数组很容易得到每个父节点和其子节点的关系，假设数组的起始下标为0，那么有：

PARENT(i) = (i - 1) / 2  --> 如下标1和2的数组元素，其父节点是下标0的元素。
LEFT_CHILD(i) = (i * 2) + 1   
RIGHT_CHILD(i) = (i * 2) + 2  -->如下标为0的数组元素，其左右子节点的下标分别是1和2。

因此可以直接在程序中定义：

#define PARENT(i) ((i - 1) >> 1)
#define LEFT_CHILD(i) (((i) << 1) + 1)
#define RIGHT_CHILD(i) (((i) << 1 ) + 2)

二、最大堆和最小堆

堆有最大堆和最小堆之分，在最大堆中，除了根节点以外的所有节点i都要满足：A[PARENT[i]] >= A[i]，所有的子节点的值不会超过其父节点的值。因此，在最大堆中，最大的元素存放在根节点中。

而最小堆和最大堆相反，除了根节点以外的所有节点i都要满足：A[PARENT[i]] <= A[i]， 所有子节点的值都大于等于其根节点的值。因此，最小堆中根节点的元素是最小的。

在堆排序算法中，使用的是最大堆，最小堆通常用于构造优先级队列。

以最大堆为例，其包含的操作为：

• MAX_HEAPIFY：用来维护一个最大堆。
• BUILD_MAX_HEAP：从一堆无序的数组中构造出一个最大堆。
• HEAPSORT：执行一次堆排序过程。

三、最大堆

3.1 维护最大堆

把一个堆构造成最大堆的流程：

1. 从A[i], A[LEFT[i]], A[RIGHT[i]]中选出最小的，保存其下标largest
2. 如果largest不等于i，交换A[i]和A[largest]

以下图为例，当前堆中4处于一个非正确的位置：

首先把4和其儿子中最大的14交换，得到以下堆：

交换后4依旧不是最小的元素，继续交换4和8：

4当前已经是叶子节点了，此时对4的最大堆化操作就完成了。并且此时的堆也就是一个最大堆。

不难看出：对一个高度为h的树来说，这个操作的时间复杂度为O(h)。

对应的c代码：

static void _max_heapify(int *data, const uint len, const uint i) {
    unsigned int lchild, rchild;
    unsigned int largest;

    lchild = LEFT_CHILD(i);
    rchild = RIGHT_CHILD(i);

    // 得到父子节点中最小的元素
    if (lchild < len && data[i] < data[lchild])
        largest = lchild;
    else
        largest = i;

    if (rchild < len && data[largest] < data[rchild])
        largest = rchild;

    // 交换最小的元素
    if (i != largest) {
        swap_int(&data[i], &data[largest]);
        _max_heapify(data, len, largest);
    }
}

3.2 建堆

建堆的过程实际上是执行多次MAX_HEAPIFY，我们只需对2/n以内的元素都执行MAX_HEAPIFY操作即可完成一个最大堆的构建。

因为[n/2, n)之间的元素都是叶子节点，所以无需对它们进行转换操作。

要注意的是建堆必须从下往上，否则可能出现堆只是局部有效，对全局而言并非有效：

以上图为例，如果从上到下建堆，在调整完4的位置之后，14被放在了树根。而实际上被放在树根的应该是16，因为接下来就不会调整14了，它的位置就永远不对，这个堆也就不是一个符合要求的堆。

代码：

static void _build_max_heap(int *data, const uint len) {
    int i;
    for (i = (len / 2) - 1; i >= 0; i--) {
        _max_heapify(data, len, i);
    }
}

四、堆排序

参考：排序算法之堆排序