大顶堆和小顶堆

1. 什么是堆、大顶堆和小顶堆

堆是一种非线性结构，可以把堆看作一棵二叉树，也可以看作一个数组，即：堆就是利用完全二叉树的结构来维护的一维数组。

堆可以分为大顶堆和小顶堆：
大顶堆：每个结点的值都大于或等于其左右孩子结点的值。
小顶堆：每个结点的值都小于或等于其左右孩子结点的值。
用简单的公式来描述一下堆的定义就是：

• 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

• 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

如果是排序，求升序用大顶堆，求降序用小顶堆。一般我们说 topK 问题，就可以用大顶堆或小顶堆来实现，即最大的 K 个：小顶堆/最小的 K 个：大顶堆。

2. 大顶堆的构建过程

大顶堆的构建过程就是从最后一个非叶子结点开始从下往上调整。

最后一个非叶子节点怎么找？这里我们用数组表示待排序序列，则最后一个非叶子结点的位置是：数组长度/2-1。假如数组长度为9，则最后一个非叶子结点位置是 9/2-1=3。

1. 比较当前结点的值和左子树的值，如果当前节点小于左子树的值，就交换当前节点和左子树；
   交换完后要检查左子树是否满足大顶堆的性质，不满足则重新调整子树结构；
2. 再比较当前结点的值和右子树的值，如果当前节点小于右子树的值，就交换当前节点和右子树；
   交换完后要检查右子树是否满足大顶堆的性质，不满足则重新调整子树结构；
3. 无需交换调整的时候，则大顶堆构建完成。

画个图理解下，以 [3, 7, 16, 10, 21, 23] 为例：

3. 大顶堆的排序过程

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值，如此反复执行，便能得到一个有序序列了。

该排序过程可以用下面 4 步概括：
第 1 步：先 n 个元素的无序序列，构建成大顶堆；
第 2 步：将根节点与最后一个元素交换位置，（将最大元素"沉"到数组末端）；
第 3 步：交换过后可能不再满足大顶堆的条件，所以需要将剩下的 n-1 个元素重新构建成大顶堆；
第 4 步：重复第 2 步、第 3 步直到整个数组排序完成。

同样以 [3, 7, 16, 10, 21, 23] 为例：

4. 程序实例

#include <stdio.h>
void g1(int *a, int n, int i){
    while (2 * i <= n){
        int j = 2 * i;
        int v = a[j - 1];
        if (j < n && v < a[j]){
            v = a[j];
            j += 1;
        }
        if (a[i - 1] < v){
            int tmp = a[i - 1];
            a[i - 1] = v;
            a[j - 1] = tmp;
            i = j;
        } else{
            break;
        }
    }
}
int g2(int *a, int n, int m){
    int i;
    for (i = n / 2; i > 0; --i)
        g1(a, n, i);
    for (i = 0; i < n && a[i] != m; ++i);
    int j = 0;
    for (++i; i > 0; i /= 2)
        ++j;
    return j;
}
int main(int argc, char* argv[]){
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
    int n = sizeof(a) / sizeof(a[0]);
    printf("%d", g2(a, n, 8));
    return 0;
}

g1 函数的作用即为构建大顶堆，代码第29行：当 i = 7 时，a[i] = 8，退出循环，程序执行后控制台输出 j 的值为：4。