堆结构

用数组 heap[0..n-1] 存储完全二叉树：parent=(i-1)//2，left=2i+1，right=2i+2。

• 插入：尾部追加，sift_up。
• 删除堆顶：末尾换到顶再 sift_down。
• Python：heapq 为小根堆；大根堆存负值或自定义比较。

import heapq
小根堆
h = []
heapq.heappush(h, 3)
heapq.heappush(h, 1)
x = heapq.heappop(h)  # 1
Top K 最大：维护大小 k 的小根堆
def top_k(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)
    for x in nums[k:]:
        if x > heap[0]:
            heapq.heapreplace(heap, x)
    return heap

优先队列抽象

按优先级出队，底层即堆。Dijkstra、Prim、任务调度、合并 K 个有序链表都用小根堆按当前最小边/距离/节点值弹出。

合并 K 路有序链表：

def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    dummy = cur = ListNode(0)
    while heap:
        _, i, node = heapq.heappop(heap)
        cur.next = node
        cur = cur.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

数据流中位数

对顶堆：左侧大根堆存较小一半，右侧小根堆存较大一半，保持 |len(left)-len(right)| <= 1，中位数为堆顶或两堆顶平均。插入时 O(log n)。

与其他结构对比

| 需求 | 结构 | |---|---| | 全局最值动态 | 堆 | | 有序集合全序 | 平衡 BST / TreeMap | | 仅最值一次 | 扫描 O(n) |

练习：215、347、23、295、703。面试写 heapq 时注明小根堆语义及 tuple 比较规则（避免节点对象不可比）。