[数据结构]堆

堆的定义

堆必须是一个完全二叉树

允许二叉树的最后一行不为满
最后一行的顺序必须是从左往右
最后一行元素之间不可以有间隔

堆依照堆序性可以分为大根堆和小根堆：

堆的存储

这里以大根堆为例，从上到下，从左往右进行编号，按照编号保存到对应的数组中：

若节点下标为 i，左子节点下标为 2i + 1，右子下标为 2i + 2

堆的基本操作

这两个操作不同的翻译或者教材有不同的叫法

下滤

以大根堆为例，将破坏堆序性的根节点元素跟它的最大的子节点比较，如果小于它的最大子节点，则与之交换，持续比较交换，直到这个元素大于它的两个子节点（或者到底部）为止。

这个操作一般用于构建堆，下滤操作的复杂度为 O(logN)

上滤

以大根堆为例，将破坏堆序性的叶子节点元素，让它和它的父节点比较，若大于父元素则交换，直到小于它的父元素或者成为根节点为止。

这个一般用于插入元素到堆中，上滤操作的复杂度为 O(logN)

建堆的基本方法

自顶向下法

对应的操作为上滤，将元素一个一个插入到堆内，复杂度为 O(NlogN)

自下而上法

对应的操作为下滤，对倒数第二排的子树开始进行下滤操作，直到整体根节点下滤完毕，复杂度为 O(N)

堆的具体应用

优先队列

优先队列有两个基本操作：

插入队列；

弹出最小元素；

这种数据结构可以用小根堆来实现，因为小根堆的根节点本来就是最小元素，直接弹出根节点，就会将剩下的元素调整成堆（只须将最后一个元素放到根节点，然后进行下滤操作），弹出的复杂度为 O(logN)。插入队列的操作就是插入到尾部进行上滤操作，复杂度为 O(logN)。

💡

堆排序堆排序只需要建最小堆（如果是从小到大排序），然后一次弹出最小元素即可。但考虑到空间复杂度需要原地排序，那么直接使用大根堆，大根堆的索引顺序和元素的大小的顺序刚好是匹配的。

https://www.bilibili.com/video/BV1AF411G7cA

C++ 中的 priority_queue

C++ 的模板库自带了优先队列，是一个大根堆，在弹出根节点后会自动完成堆的重建。


#include <queue>

int main() {
    // 创建一个存储整数的优先队列，默认为最大堆
    std::priority_queue<int> pq;

    // 插入元素
    pq.push(10);
    pq.push(30);
    pq.push(20);

    // 获取最高优先级的元素
    int highestPriority = pq.top();
    std::cout << "Highest priority element: " << highestPriority << std::endl;

    // 弹出最高优先级的元素
    pq.pop();

    // 再次获取最高优先级的元素
    highestPriority = pq.top();
    std::cout << "Highest priority element after pop: " << highestPriority << std::endl;

    return 0;
}