7. 堆（Heap / 优先队列）

问题：需要快速获取最大（或最小）元素，如任务优先级调度、Top K 问题。

核心：用数组表示一棵完全二叉树，满足堆性质——每个节点 ≥（或 ≤）其子节点。根节点始终是最大（或最小）值。

特点

完全二叉树，用数组存储（parent = (i-1)/2, left = 2i+1, right = 2i+2）
最大堆：根最大；最小堆：根最小
插入和删除 O(log n)，获取极值 O(1)

优点

O(1) 获取最大/最小值
O(log n) 插入和删除极值
原地排序（堆排序 O(n log n)，O(1) 额外空间）
适合 Top K、合并有序流等场景

缺点

不支持 O(1) 随机访问特定元素（非极值）
查找任意元素 O(n)
堆不是完全有序的（中序遍历不保证有序）
实现比数组和栈复杂

// 最小堆
class MinHeap {
  #data = [];

  push(val) {
    this.#data.push(val);
    this.#bubbleUp(this.#data.length - 1);
  }

  pop() {
    const top = this.#data[0];
    const last = this.#data.pop();
    if (this.#data.length > 0) {
      this.#data[0] = last;
      this.#sinkDown(0);
    }
    return top;
  }

  peek() { return this.#data[0]; }
  get size() { return this.#data.length; }

  #bubbleUp(i) {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.#data[i] >= this.#data[parent]) break;
      [this.#data[i], this.#data[parent]] = [this.#data[parent], this.#data[i]];
      i = parent;
    }
  }

  #sinkDown(i) {
    const n = this.#data.length;
    while (true) {
      let min = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < n && this.#data[l] < this.#data[min]) min = l;
      if (r < n && this.#data[r] < this.#data[min]) min = r;
      if (min === i) break;
      [this.#data[i], this.#data[min]] = [this.#data[min], this.#data[i]];
      i = min;
    }
  }
}

// Top K 问题：找数组中最大的 K 个元素
function topK(arr, k) {
  const heap = new MinHeap();
  for (const val of arr) {
    heap.push(val);
    if (heap.size > k) heap.pop(); // 弹出最小的
  }
  return heap.peek(); // 第 K 大的值
}

const nums = [3, 2, 1, 5, 6, 4];
console.log(topK(nums, 2)); // 5（第 2 大的值）

package heap

import "container/heap"

// 定义最小堆元素
type Item struct {
    Value int
}

type MinHeap []*Item

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].Value < h[j].Value }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x any) {
    *h = append(*h, x.(*Item))
}

func (h *MinHeap) Pop() any {
    old := *h
    n := len(old)
    item := old[n-1]
    *h = old[:n-1]
    return item
}

// 使用示例
func Example() {
    h := &MinHeap{}
    heap.Init(h)

    heap.Push(h, &Item{Value: 5})
    heap.Push(h, &Item{Value: 3})
    heap.Push(h, &Item{Value: 7})

    top := heap.Pop(h).(*Item)
    _ = top.Value // 3（最小值）
}

Go 的 container/heap 提供堆接口；JS 没有内置堆，通常自己实现或用第三方库。堆排序是唯一能做到 O(1) 额外空间 + O(n log n) 的比较排序。