向下调整算法

首先声明这个算法的使用条件，该算法适用于除了堆顶外的其他部分都满足小堆或大堆的条件时，可以使用，简单来说就是pop堆顶的时候可以使用

使用的原理也相当简单，假设我们这里是小堆，那么堆顶元素被弹出，此时堆中第二小的元素一定是这个堆顶元素的儿子，那么我们就让堆的最后一个叶子来充当这个新的堆顶，这样可以在保持堆整体的构造不变的前提下还能把堆顶元素弹出，紧接着就让这个堆顶元素和下面的儿子进行比较，谁小谁就是新的堆顶，进行交换后第二小的元素就产生了，当然，如果树的高度很高，那么交换后可能需要继续交换，知道这个叶子回到最后一层，这个过程也是可以借助循环实现的，借助这个向下调整算法就可以把堆顶元素弹出的同时还能变成一个新堆，不断的找出最小的值或最大的值

那么下面我们来实现这个算法

void AdjustDown(HP* php, int n, int parent)
{
   
    assert(php);
    int child = parent * 2 + 1;
    while (child < n)
    {
   
        if (child + 1 < n && php->a[child + 1] < php->a[child])
        {
   
            child++;
        }
        if (php->a[child] < php->a[parent])
        {
   
            Swap(&php->a[child], &php->a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
   
            break;
        }
    }
}

void HeapPop(HP* php)
{
   
    assert(php);
    Swap(&php->a[0], &php->a[php->size - 1]);
    php->size--;

    AdjustDown(php, php->size, 0);
}

堆的应用

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆
   升序：建大堆
   降序：建小堆
2. 利用堆删除思想来进行排序
   建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
   TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
   比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
   对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能
   数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
3. 用数据集合中前K个元素来建堆
   前k个最大的元素，则建小堆
   前k个最小的元素，则建大堆
4. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
   剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

void PrintTopK(int* a, int n, int k)
{
   
// 1. 建堆--用a中前k个元素建堆
// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
}
void TestTopk()
{
   
int n = 10000;
int* a = (int*)malloc(sizeof(int)*n);
srand(time(0));
for (size_t i = 0; i < n; ++i)
{
   
a[i] = rand() % 1000000;
}
a[5] = 1000000 + 1;
a[1231] = 1000000 + 2;
a[531] = 1000000 + 3;
a[5121] = 1000000 + 4;
a[115] = 1000000 + 5;
a[2335] = 1000000 + 6;
a[9999] = 1000000 + 7;
a[76] = 1000000 + 8;
a[423] = 1000000 + 9;
a[3144] = 1000000 + 10;
PrintTopK(a, n, 10);
}