堆

想象你在排队买奶茶，但队伍规则不是先来后到，而是“谁最急谁先买”——比如老人、孕妇优先。这种特殊的队列就叫优先队列：每个元素有一个“优先级”，优先级最高的元素总是最先被取出。

堆（Heap）就是实现优先队列最常用的一种数据结构。它是一棵特殊的树，能保证每次都能快速找到并取出最大（或最小）的元素。

堆是一棵完全二叉树：除了最后一层，其他层都是满的，最后一层的节点都靠左排列。这种结构很紧凑，没有空洞。

完全二叉树可以用一个数组来存储，不需要指针。根节点放在下标1（或0），然后利用下标公式快速定位父子节点：

• 节点 i 的左孩子下标：2*i（如果从1开始）
• 节点 i 的右孩子下标：2*i+1
• 节点 i 的父节点下标：i/2（整数除法）

这种存储方式节省空间，而且通过下标计算就能在树中上下移动，非常高效。

往堆里插入一个新元素时，先把它放在数组的末尾（也就是完全二叉树的最后一个位置）。

然后让这个新元素“上浮”（bubble up）：不断和它的父节点比较，如果新元素优先级更高（比如更大），就交换位置，直到它到达正确的位置（比父节点小/大，或者成为根节点）。

这个过程保证了堆的性质：每个父节点都比子节点优先级高（大顶堆）或低（小顶堆）。

删除堆顶（即优先级最高的元素）时，先把堆顶元素取走，然后把数组最后一个元素移到堆顶位置，这样堆的大小减1。

接着让这个新堆顶元素“下沉”（sink down）：和它的左右孩子中优先级更高的那个比较，如果它比孩子小（大顶堆），就和那个孩子交换，然后继续下沉，直到它比所有孩子都大（或成为叶子节点）。

这样堆的性质就恢复了，而且操作非常快。

典型用途：

• Top K 问题：比如从海量数据中找出最大的K个数。维护一个大小为K的小顶堆，遍历数据，如果当前元素比堆顶大，就替换堆顶并下沉，最后堆里就是最大的K个。
• 合并有序序列：把每个序列的第一个元素放入堆，每次取出堆顶（最小元素），然后从对应序列取下一个元素入堆，直到所有序列合并完毕。
• 堆排序、Dijkstra最短路径等算法也依赖堆。