堆与优先队列

堆（Heap）是一种特殊的完全二叉树：大顶堆满足父节点 ≥ 子节点，小顶堆满足父节点 ≤ 子节点，堆顶永远是全局最大（小）值。优先队列就是基于堆实现的：每次弹出的都是优先级最高的元素。定时任务调度、Dijkstra 最短路、求 TopK 都依赖它，是面试高频数据结构。

大顶堆与小顶堆

• 大顶堆：父 ≥ 子，堆顶是最大值，适合求「最小的 K 个」。
• 小顶堆：父 ≤ 子，堆顶是最小值，适合求「最大的 K 个」。

堆只保证「父子有序」，不保证兄弟之间有序，因此它不是全局有序结构。

       大顶堆                 小顶堆
         9                      1
        / \                    / \
       6   8                  3   5
      / \                    / \
     4   3                  7   8

用数组存储堆

堆是完全二叉树，所以可以像数组一样连续存放，不需要指针。若节点下标为 i，则左孩子是 2i+1、右孩子是 2i+2、父节点是 (i-1)/2。上面小顶堆对应的数组为 [1, 3, 5, 7, 8]。

下标:  0   1   2   3   4
值:    1   3   5   7   8
       节点 3（下标1）的孩子 = 下标 3、4，即 7 和 8 ✔

插入（上浮）与删除堆顶（下沉）

• 插入：新元素先放到数组末尾，然后不断与父节点比较，不满足堆序就交换，直到上浮到正确位置。
• 删除堆顶：把堆顶与最后一个元素交换，弹出堆顶后，再从根开始与较大的孩子（大顶堆）交换下沉，恢复堆序。

向小顶堆 [1,3,5,7,8] 插入 0：
1) 放末尾:  1 3 5 7 8 0
2) 0 与父 5 交换:  1 3 0 7 8 5
3) 0 与父 1 交换:  0 3 1 7 8 5   ← 堆顶又变成最小值

上浮或下沉最多走完整个树高，代价 O(log n)。

优先队列的工程实现

优先队列 = 堆 + 每次弹出最值。Python 的 heapq、Java 的 PriorityQueue、Go 的 container/heap 都内置了堆操作：

import heapq
heap = [3, 1, 4, 1, 5]
heapq.heapify(heap)          # 原地建小顶堆
heapq.heappush(heap, 0)      # 插入 0
print(heapq.heappop(heap))   # 输出：0，弹出最小值
print(heapq.heappop(heap))   # 输出：1

复杂度与面试要点

操作	时间复杂度
取堆顶	O(1)
插入 / 删除堆顶	O(log n)
建堆	O(n)
堆排序	O(n log n)

• 高频题：数组第 K 大元素（维护大小为 K 的小顶堆）、合并 K 个有序链表、数据流中位数（大顶堆 + 小顶堆）。
• TopK 口诀：「求最大 K 个用小顶堆、求最小 K 个用大顶堆」，堆里始终只留 K 个，整体 O(n log K)。
• 面试易错点：堆只能保证堆顶最值，不能当作有序数组遍历；兄弟之间是无序的。

小结：堆用完全二叉树保证「堆顶最值、增删 O(log n)、建堆 O(n)」，是优先队列与 TopK 问题的标准答案；记住上浮下沉、数组下标与那张复杂度表即可。