数据结构—堆

认识堆

堆的概念和特性

先解释一下堆（Heap）的概念，堆是一种数据结构，堆的定义：

堆中某个结点的值总是不大于或不小于其父结点的值；
堆总是一棵完全二叉树；

由堆的定义可以得到，堆顶是最大值或者最小值。

堆的基本操作

由于堆存储在下标从0开始计数的数组中，因此，在堆中给定下标为i的结点时：
如果 i = 0，结点 i 是根结点，无父结点；否则结点 i 的父结点为结点 [(i - 2) / 2]
如果 2i + 1 > n - 1，则结点 i 无左子女；否则结点 i 的左子女为结点 2i + 1
如果 2i + 2 > n - 1，则结点 i 无右结点；否则结点 i 的右子女为结点 2i + 2

初建堆

建堆的算法是（假设建大堆）

从后往前找第一个非叶子结点：(len >> 1) - 1;，从该结点开始往前遍历到根结点，进行下面处理
对该结点向下调整，如果该结点比子结点小，就把该结点跟子节点互换。替换后的子结点继续向下调整。直到条件不满足或者该结点成为了叶子结点。

建堆的时间复杂度n - log₂(n + 1)，可得渐进复杂度为 O(n)（堆排序中建堆过程时间复杂度O(n)怎么来的？)
建堆代码如下（CommonHead.h）：

#include <assert.h>
#include "CommonHead.h"

void AdjustDown(int* arr, const size_t& len, const unsigned& index, HeapType type = BIG_HEAP)
{
    unsigned node_index = index;
    unsigned child = (node_index << 1) + 1; // 左孩子

    while (child < len)
    {
        const unsigned r_child = child + 1;
        if (child + 1 < len)
        {
            switch (type)
            {
            case BIG_HEAP:
                child = arr[child] >= arr[r_child] ? child : r_child;
                break;
            case SMALL_HEAP:
                child = arr[child] <= arr[r_child] ? child : r_child;
                break;
            default:
                break;
            }
        }
        if (BIG_HEAP == type && arr[node_index] < arr[child] || SMALL_HEAP == type && arr[node_index] > arr[child])
        {
            Swap(arr[node_index], arr[child]);
            node_index = child;
            child = (node_index << 1) + 1;
        }
        else
        {
            break;
        }
    }
}

void BuildHeap(int* arr, const size_t& len, HeapType type = BIG_HEAP)
{
    assert(arr && len > 0);
    for (int i = (len >> 1) - 1; i >= 0; --i)
    {
        AdjustDown(arr, len, i, type);
    }
}

堆的插入

堆的插入和查找的时间复杂度为log(n)
算法就是插到堆尾，然后向上调整，结点的父节点为：(index - 1) >> 1。假设建个大堆，插入结点如果比父节点大，就互换。父节点也一样向上调整，直到条件不满足或者新结点成为了跟结点。
算法简单，就不列代码了。

堆的删除

堆的删除比较麻烦，如果只是删除堆顶，可以把最后一个结点放在堆顶位置，然后做向下调整，这是一次log(n)。如果是随机删除一个元素，需要重新建堆。

堆的应用：

堆的应用包括：堆排序、解决海量数据topk问题、优先级队列、动态数据取中位数、

堆排序

升序构建大堆，降序构建小堆。

1.初建堆
2.堆顶和第k个元素交换，再调整堆(k为n到0）

#include <ctime>
#include <assert.h>
#include "CommonHead.h"

void AdjustDown(int* arr, const size_t& len, const unsigned& index, HeapType type = BIG_HEAP)
{...}

void BuildHeap(int* arr, const size_t& len, HeapType type = BIG_HEAP)
{...}

void HeapSort(int* arr, const size_t& len, bool reverse = false)
{
    assert(arr && len > 0);
    auto type = reverse ? SMALL_HEAP : BIG_HEAP;
    BuildHeap(arr, len, type);
    for (auto i = len - 1; i > 0; --i)
    {
        Swap(arr[i], arr[0]);
        AdjustDown(arr, i, 0, type);
    }
}
int main()
{
    srand((int)time(0));  // 产生随机种子
    int arr[ARRAY_LEN];
    for (auto i = 0; i < ARRAY_LEN; ++i)
    {
        arr[i] = i;
    }
    PRINT_ARR(arr);
    Shuffle(arr, ARRAY_LEN);
    PRINT_ARR(arr);
    HeapSort(arr, ARRAY_LEN, true);
    PRINT_ARR(arr);

    return 0;

}

解决海量数据topk问题

小堆可以找到最大的k个数据。方法是前k个数据建立一个小堆，再来数据就跟堆顶比较，如果比对顶小就淘汰，如果比堆顶大就替换堆顶，然后调整堆。同理，大堆可以找到最小的k个数据

优先级队列

优先级队列（PriorityQueue）是队列的变种，我们知道队列一般是FIFO，优先级队列是根据元素的优先级来选择哪个结点。而堆恰好是可以高效实现优先级队列的数据结构。

当要取优先级队列数据时，直接取堆顶，把最后一个结点放堆顶，再对堆顶做向下调整
当要往优先级队列塞数据时，直接塞到最后，再对新结点向上调整即可

动态数据取中位数

对于一直在新增的数据，如果要比较快的取中位数，我们可以动态维护一个有序列表。插入数据时用折半插入，查找时用二分查找。但是当数据量变得很庞大时，二分查找也满足不了我们的需求，这个时候就可以借用堆来实现。

动态维护两个堆，所有结点个数为n：

一个大堆、一个小堆
大堆的结点都小于等于小堆的结点
大堆的结点数量等于或者大于1个小堆的结点数量
n为偶数时，两个堆顶就是中位数；n为奇数时，大堆的堆顶就是中位数。时间复杂度为O(1)

新增一个元素a：
1、如果新增前的n为奇数且a大于等于小堆堆顶，则把a插入小堆
2、如果新增前的n为偶数且a大于等于小堆堆顶，则a顶替小堆的堆顶，调整小堆，再把原小堆的堆顶插入大堆。
3、如果新增前的n为偶数且a小于小堆堆顶，就直接插入大堆
4、如果新增前的n为奇数且a小于小堆堆顶，则a顶替大堆的堆顶，调整大堆，再把原大堆的堆顶插入小堆
新增元素的时间复杂度是O(logn)

删除一个元素的话，就需要判断两个堆的大小，如果有必要就进行迁移，时间复杂度是O(logn)

注意：如果我们有一个变量记录当前的中位数在哪个堆顶的话，上面情况2的a直接插入小堆即可，少了一次O(logn)的操作

top百分k问题：
这是前面topk问题和取中位数的变种，比如1000个数据，排名刚好是70%的数据就是排名第700的数据。
解决方案就是大小堆的变种，小堆存n * k * 0.01个数据，大堆存n - n * k * 0.01个数据，以此类推即可求得。