堆与优先队列

优先队列回答的问题："在 $n$ 个元素里反复取最值"。排序一次太贵，线性扫描每次 $O(n)$ 太慢；堆用完全二叉树把它降到 $O(\log n)$ 。它是 Dijkstra、Prim、任务调度、Top-K 的公共部件（→ 最短路径）。

二叉堆

二叉堆用数组隐式表示完全二叉树：下标 $i$ 的孩子是 $2i+1$ 与 $2i+2$ ，父亲是 $\lfloor(i-1)/2\rfloor$ 。堆性质：每个父亲 $\le$ （或 $\ge$ ）其孩子——于是最小值恒在根（下标 0）。

操作	复杂度	做法
取最小	$O(1)$	看根
删除最小	$O(\log n)$	尾元素补根，逐层下滤（sift-down）
插入	$O(\log n)$	追加到尾，逐层上滤（sift-up）
建堆	$O(n)$	从最后一个非叶节点倒序下滤
按下标访问	不支持	堆只承诺"根最小"，不支持随机查询

建堆是 $O(n)$ 而非 $O(n \log n)$ ：一半节点是叶子不用动，多数节点只下沉一两层，求和后线性。这是堆在"把无序数组变成优先队列"上的一次意外便宜。

import heapq

# Top-K：维护大小为 k 的最小堆
def top_k(nums, k):
    heap = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)
    return sorted(heap, reverse=True)

堆的变体

d 叉堆：每个节点 $d$ 个孩子，树更矮更宽——插入更快、下滤更贵，适合插入多删除少的负载。
索引优先队列：堆 + 元素到堆位置的映射，支持 $O(\log n)$ 的修改与删除任意元素——Dijkstra 的 decrease-key 需要它。
斐波那契堆：insert 与 decrease-key 均摊 $O(1)$ ，理论最优；常数大、实现复杂，实践中少见，主要是理论价值（改进 Dijkstra 的界）。
配对堆：实现简单、实践中表现好，是许多库的折中选择。

什么时候不用堆

只要一次最值：直接线性扫描 $O(n)$ ，建堆反而多余；
只要静态排序： heapsort 是 $O(n \log n)$ 但缓存不友好；现代 CPU 上快排类更常胜（→ 排序与查找）；
需要按序访问全部：平衡树（→ 二叉搜索树与平衡树）支持范围查询与按序遍历，堆只支持最值。

本章要点

堆用数组隐式表示完全二叉树；堆性质保证最小值在根
插入/删除 $O(\log n)$ ；建堆 $O(n)$ ——多数节点只下沉一两层
堆不支持随机访问与按序遍历；需要这些用平衡树
索引优先队列支持 decrease-key，是 Dijkstra 的标配
Top-K 用大小为 k 的最小堆： $O(n \log k)$ 优于全排序