堆与优先队列

堆是基于完全二叉树的优先队列结构，支持快速获取最值。

核心性质

• 结构性：完全二叉树，可用数组紧凑存储（索引 的左子 、右子 、父 ）
• 堆序性：大顶堆（父 ≥ 子）或小顶堆（父 ≤ 子）

关键操作

操作	复杂度	过程
入堆 (push)		尾部插入 → 向上冒泡（sift-up）
出堆 (pop)		取堆顶 → 尾元素替换 → 向下堆化（sift-down）
建堆 (heapify)		从最后一个非叶节点倒序 sift-down
取堆顶 (peek)		直接读取 array[0]

应用

• 堆排序：建堆 + 反复出堆， 原地排序
• Top-K 问题：维护大小为 K 的小顶堆
• Dijkstra 最短路径：用小顶堆加速选最小距离节点
• 合并 K 个有序链表