代码随想录 — 堆与优先队列

补充专题：堆（Heap）/ 优先队列（Priority Queue）是面试高频数据结构，常用于 TopK、数据流中位数、Dijkstra 等场景。

---

一、堆的理论基础

• 定义：堆是一棵完全二叉树，满足堆序性质：
  • 最大堆（大顶堆）：每个节点 ≥ 其子节点 → 堆顶是最大值。
  • 最小堆（小顶堆）：每个节点 ≤ 其子节点 → 堆顶是最小值。
• 存储：用数组表示，父节点 i 的左子 2i+1、右子 2i+2；子节点 i 的父 Math.floor((i-1)/2)。
• 核心操作：
  • 上浮（sift up）：插入元素到末尾后向上调整，时间 O(log n)。
  • 下沉（sift down）：取出堆顶后把末尾元素放到堆顶，向下调整，时间 O(log n)。
  • 建堆：从最后一个非叶节点开始依次下沉，时间 O(n)。
• 语言支持：
  • JavaScript：无内置堆，需手写或用第三方库。
  • Python：heapq 模块（默认最小堆）；最大堆可取反。
  • Java：PriorityQueue（默认最小堆）。

---

二、常见题目与思路

题目	思路要点	复杂度
215 数组中第 K 大元素	维护大小为 k 的小顶堆，遍历完后堆顶即第 K 大；或用快速选择 O(n) 平均。	O(n log k)
347 前 K 个高频元素	先用 Map 统计频率，再用大小为 k 的小顶堆按频率排序，堆顶是当前第 k 大频率，超过 k 就弹出。	O(n log k)
295 数据流的中位数	用大顶堆存较小一半 + 小顶堆存较大一半；插入时保持两堆平衡（大小差 ≤ 1）；中位数从堆顶取。	插入 O(log n)，查询 O(1)
23 合并 K 个升序链表	把 k 个链表头放入小顶堆，每次取堆顶（最小），其 next 入堆。	O(N log k)，N 为总节点数
239 滑动窗口最大值	可用大顶堆（需懒删除过期元素）；更优方案是单调队列。	堆：O(n log n)
703 第 K 大元素（数据流）	维护大小为 k 的小顶堆，新元素大于堆顶才替换。	插入 O(log k)
Dijkstra 堆优化	用小顶堆存 (距离, 节点)，每次取最小距离节点松弛邻居。	O((V+E) log V)

---

三、核心代码模板

最小堆（JavaScript 手写）

class MinHeap {
  constructor() { this.heap = []; }

  size() { return this.heap.length; }
  peek() { return this.heap[0]; }

  push(val) {
    this.heap.push(val);
    this._siftUp(this.heap.length - 1);
  }

  pop() {
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length) {
      this.heap[0] = last;
      this._siftDown(0);
    }
    return top;
  }

  _siftUp(i) {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.heap[parent] <= this.heap[i]) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }

  _siftDown(i) {
    const n = this.heap.length;
    while (2 * i + 1 < n) {
      let smallest = 2 * i + 1;
      if (smallest + 1 < n && this.heap[smallest + 1] < this.heap[smallest]) smallest++;
      if (this.heap[i] <= this.heap[smallest]) break;
      [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
      i = smallest;
    }
  }
}

第 K 大元素（215）

// JavaScript — 小顶堆，时间 O(n log k)
function findKthLargest(nums, k) {
  const heap = new MinHeap();
  for (const num of nums) {
    heap.push(num);
    if (heap.size() > k) heap.pop();
  }
  return heap.peek();
}

Python — 使用 heapq

import heapq

# 第 K 大元素 — 时间 O(n log k)
def find_kth_largest(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

# 前 K 个高频元素 — 时间 O(n log k)
def top_k_frequent(nums, k):
    from collections import Counter
    count = Counter(nums)
    return heapq.nlargest(k, count.keys(), key=count.get)

# 数据流中位数
class MedianFinder:
    def __init__(self):
        self.small = []  # 大顶堆（取反）
        self.large = []  # 小顶堆

    def addNum(self, num):
        heapq.heappush(self.small, -num)
        heapq.heappush(self.large, -heapq.heappop(self.small))
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def findMedian(self):
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

合并 K 个升序链表（23）

// JavaScript — 时间 O(N log k)
function mergeKLists(lists) {
  const heap = new MinHeap(); // 需修改比较逻辑为比较 node.val
  // 简化版：使用数组 + 排序模拟（面试时可手写堆）
  const dummy = new ListNode(0);
  let cur = dummy;
  // 将所有头节点入堆
  for (const head of lists) if (head) heap.push(head);
  while (heap.size()) {
    const node = heap.pop();
    cur.next = node;
    cur = cur.next;
    if (node.next) heap.push(node.next);
  }
  return dummy.next;
}

---

四、堆与优先队列总结

场景	用法
求第 K 大/小	维护大小为 k 的反向堆
数据流统计	对顶堆（大顶堆 + 小顶堆）
多路归并	小顶堆存各路当前最小
贪心调度	按优先级取最优（Dijkstra、任务调度器）

建议：JavaScript 面试时可能需要手写最小堆，务必熟练；Python 直接用 heapq 即可。理解「堆顶是什么」「何时入堆何时出堆」是关键。