堆

堆是一种满足特定条件的完全二叉树，其中大顶堆中任意节点的值大于等于其子节点的值，小顶堆中任意节点的值小于等于其子节点的值。

其具有一下特点：

• 最底层节点靠左填充，其他层的节点都被填满
• 我们将二叉树的根节点称为“堆顶”，将底层最靠右的节点称为“堆底”
• 对于大顶堆（小顶堆），堆顶元素（根节点）的值是最大（最小）的

堆的常用操作

堆通常用于实现优先队列，大顶堆相当于元素按从大到小的顺序出队的优先队列。从使用角度来看，我们可以将“优先队列”和“堆”看作等价的数据结构。

C未直接提供heap类，C++代码如下：

priority_queue<int,vector<int>,greater<int>>minHeap;   // 小顶堆
priority_queue<int,vector<int>,less<int>maxHeap>;      // 大顶堆

// 元素入堆
maxHeap.push(1);
maxHeap.push(3);
maxHeap.push(2);
maxHeap.push(5);
maxHeap.push(4);

// 获取堆顶元素
int peek = maxHeap.top(); // 5

// 出堆元素会形成一个从大到小的序列
maxHeap.pop(); // 5
maxHeap.pop(); // 4
maxHeap.pop(); // 3
maxHeap.pop(); // 2
maxHeap.pop(); // 1

// 获取堆大小
int size=maxHeap.size();

// 判断堆是否为空
bool isEmpty=maxHeap.empty();

// 输入列表并建堆
vector<int> input{1,2,3,4,5};
priority_queue<int,vector<int>,greater<int>>minHeap(input.begin(),input.end());

堆的实现

堆的存储和表示

当使用数组表示二叉树时，元素代表节点值，索引代表节点在二叉树中的位置。节点指针通过索引映射公式来实现。给定索引$i$，其左子节点的索引为$2i+1$，右子节点的索引为$2i+2$，父节点的索引为$(i-1)/2$（向下整除）。当索引越界时，表示空节点或节点不存在。

代码实现：

// 获取左子节点的索引
int left(MaxHeap *maxHeap,int i){
    return 2*i+1;
}

// 获取右子节点的索引
int right(MaxHeap *maxHeap,int i){
    return 2*i+2;
}

// 获取父节点的索引
int parent(MaxHeap *maxHeap,int i){
    return (i-1)/2;
}

访问堆顶元素

堆顶元素即为二叉树的根节点，也就是列表的首个元素：

int peek(MazHeap*maxHeap){
    return maxHeap->data[0];
}

元素入堆

我们首先将其添加到堆底。添加之后，由于 val 可能大于堆中其他元素，堆的成立条件可能已被破坏，因此需要修复从插入节点到根节点的路径上的各个节点，这个操作被称为堆化（从底至顶）。

设节点总数为$n$，则树的高度为$O(\log n)$，故堆化操作即元素入堆操作的时间复杂度为$O(\log n)$。

void push(MaxHeap*maxHeap,int val){
    // 节点数量限制
    if(maxHeap->size==MAX_SIZE){
        printf("heap is full");
        return;
    }
    // 添加节点
    maxHeap->data[maxHeap->size]=val;
    maxHeap->size++;

    // 从底至顶堆化
    siftUp(maxHeap,maxHeap->size-1);
}
void siftUp(MazHeap*maxHeap,int i){
    while(true){
        int p=parent(maxHeap,i);        // 获取节点 i 的父节点
        // 当“越过根节点”或“节点无须修复”时，结束堆化
        if(p<0 || maxHeap->data[i]<=maxHeap->data[p]){
            break;
        }
        // 交换两节点
        swap(maxHeap,i,p);
        // 循环向上堆化
        i=p;
    }
}

堆顶元素出堆

直接从列表中删除首元素，那么二叉树中所有节点的索引都会发生变化，这将使得后续使用堆化进行修复变得困难。为了尽量减少元素索引的变动，我们采用以下操作步骤。

1. 交换堆顶元素与堆底元素（交换根节点与最右叶节点）
2. 交换完成后，将堆底从列表中删除（注意，由于已经交换，因此实际上删除的是原来的堆顶元素）
3. 从根节点开始，从顶至底执行堆化

int pop(MaxHeap*maxHeap){
    if(isEmpty(maxHeap)){
        printf("heap is empty");
        return INT_MAX;
    }
    swap(maxHeap,0,size(maxHeap)-1);            // 交换根节点与最右叶节点（交换首元素与尾元素）
    int val=maxHeap->data[maxHeap->size-1];     // 删除节点
    maxHeap->size--;
    siftDown(maxHeap,0);                        // 从顶至底堆化
    return val;                                 // 返回堆顶元素
}

void siftDown(MaxHeap*maxHeap,int i){
    while(true){
        // 判断节点 i, l, r 中值最大的节点，记为 max
        int l=left(maxHeap,i);
        int r=right(maxHeap,i);
        int max=i;
        if(l<size(maxHeap)&&maxHeap->data[l]>maxHeap->data[max]){
            max=l;
        }
        if(r<size(maxHeap)&&maxHeap->data[r]>maxHeap->data[max]){
            max=r;
        }
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if(max==i){
            break;
        }
        swap(maxHeap,i,max);  // 交换两节点
        i+max; // 循环向下堆化
    }
}

堆的应用

• 堆通常作为实现优先队列的首选数据结构，其入队和出队操作的时间复杂度均为$O(\log n)$，建堆操作为$O(n)$。
• 给定一组数据，我们可以用它们建立一个堆，然后不断地执行元素出堆操作，从而得到有序数据。然而，我们通常会使用一种更优雅的方式实现堆排序，详见“堆排序”章节。
• 获取最大的$k$个元素：例如选择热度前 10 的新闻作为微博热搜，选取销量前 10 的商品等。

建堆操作

借助入堆操作实现

首先创建一个空堆，然后遍历列表，依次对每个元素执行“入堆操作”，即先将元素添加至堆的尾部，再对该元素执行“从底至顶”堆化。

每当一个元素入堆，堆的长度就加一。由于节点是从顶到底依次被添加进二叉树的，因此堆是“自上而下”构建的。

设元素数量为$n$，每个元素的入堆操作使用$O(\log n)$时间，因此该建堆方法的时间复杂度为$O(n\log n)$。

通过遍历堆化实现

这种方法分为两步：

1. 将列表所有元素原封不动地添加到堆中，此时堆的性质尚未得到满足。
2. 倒序遍历堆（层序遍历的倒序），依次对每个非叶节点执行“从顶至底堆化”。

每当堆化一个节点后，以该节点为根节点的子树就形成一个合法的子堆。

由于叶节点没有子节点，因此它们天然就是合法的子堆，无须堆化。如以下代码所示，最后一个非叶节点是最后一个节点的父节点，我们从它开始倒序遍历并执行堆化：

MaxHeap*newMaxHeap(int nums[],int size){
    // 所有元素入堆
    MaxHeap*maxHeap=(MaxHeap*)malloc(sizeof(MaxHeap));
    maxHeap->size=size;
    memcpy(maxHeap->data,nums,size*sizeof(int));
    for(int i=parent(maxHeap,size-1);i>=0;i--){
        // 堆化除叶节点以外的其他所有节点
        siftDown(mapHeap,i);
    }
    return maxHeap;
}

输入列表并建堆的时间复杂度为$O(n)$，证明过程见原书。

Top-k问题

法一：遍历选择

通过k轮遍历，分别在每轮中提取第当前轮大的元素。

当$k<<n$时，时间复杂度为$O(nk)$，当$k$和$n$比较接近时其复杂度接近$O(n)$，很耗时。

法二：排序

对数组进行排序，提取前$k$个元素即可。但是该方法“超额”完成了任务，空间复杂度为$O(n\log n)$

法三：堆

1. 初始化一个小顶堆，其堆顶元素最小。
2. 先将数组的前 $k$ 个元素依次入堆。
3. 从第 $k+1$ 个元素开始，若当前元素大于堆顶元素，则将堆顶元素出堆，并将当前元素入堆。
4. 遍历完成后，堆中保存的就是最大的 $k$ 个元素。

// 元素入堆
void pushMinHeap(MaxHeap *maxHeap, int val) {
    push(maxHeap, -val);    // 元素取反
}

// 元素出堆
int popMinHeap(MaxHeap *maxHeap) {
    return -pop(maxHeap);    // 元素取反
}

// 访问堆顶元素
int peekMinHeap(MaxHeap *maxHeap) {
    return -peek(maxHeap);    // 元素取反
}

// 取出堆中元素
int *getMinHeap(MaxHeap *maxHeap) {
    // 将堆中所有元素取反并存入 res 数组
    int *res = (int *)malloc(maxHeap->size * sizeof(int));
    for (int i = 0; i < maxHeap->size; i++) {
        res[i] = -maxHeap->data[i];
    }
    return res;
}

// 取出堆中元素
int *getMinHeap(MaxHeap *maxHeap) {
    // 将堆中所有元素取反并存入 res 数组
    int *res = (int *)malloc(maxHeap->size * sizeof(int));
    for (int i = 0; i < maxHeap->size; i++) {
        res[i] = -maxHeap->data[i];
    }
    return res;
}

// 基于堆查找数组中最大的 k 个元素的函数
int *topKHeap(int *nums, int sizeNums, int k) {
    // 初始化小顶堆
    // 请注意：我们将堆中所有元素取反，从而用大顶堆来模拟小顶堆
    int *empty = (int *)malloc(0);
    MaxHeap *maxHeap = newMaxHeap(empty, 0);
    // 将数组的前 k 个元素入堆
    for (int i = 0; i < k; i++) {
        pushMinHeap(maxHeap, nums[i]);
    }
    // 从第 k+1 个元素开始，保持堆的长度为 k
    for (int i = k; i < sizeNums; i++) {
        // 若当前元素大于堆顶元素，则将堆顶元素出堆、当前元素入堆
        if (nums[i] > peekMinHeap(maxHeap)) {
            popMinHeap(maxHeap);
            pushMinHeap(maxHeap, nums[i]);
        }
    }
    int *res = getMinHeap(maxHeap);
    // 释放内存
    delMaxHeap(maxHeap);
    return res;
}

注：本文是作者阅读《hello算法》一书的读书笔记，内容会与原书有重合，特此声明。