什么是堆（heap），它如何实现优先级队列（priority queue）？

Question

Accepted Answer

**binary heap** 是一个完全二叉树，存储在数组中，并维持 **堆属性**：在 **min-heap** 中，每个父节点都小于等于（≤）其子节点，因此 **最小值始终位于根节点**。这使其成为实现 **priority queue** 的标准方案。

## 数组布局

```text
       1               index: 0  1  2  3  4
      / \              array: [1, 3, 5, 8, 4]
     3   5             parent(i) = (i-1)//2
    / \                left(i)   = 2i+1
   8   4               right(i)  = 2i+2
```

## 操作

```python
import heapq
h = []
heapq.heappush(h, 5)   # O(log n) — bubble up
heapq.heappush(h, 1)
heapq.heappush(h, 3)
smallest = h[0]        # peek min -> O(1)
heapq.heappop(h)       # O(log n) — remove root, sift down -> 1
```

## 时间复杂度

| 操作 | 时间 |
|---|---|
| peek min/max | O(1) |
| push (insert) | O(log n) |
| pop (extract) | O(log n) |
| build heap from n items | O(n) |

## 何时使用

- **按优先级调度**（例如 OS 任务调度器）。
- **Dijkstra / Prim** 最短路径和最小生成树算法。
- **Top-K** 问题和流式中位数。
- **Heap sort**（原地排序 O(n log n)）。

## 为什么这很重要

堆让你能够立即获得下一个最重要的元素，而无需将所有元素保持完全排序，这比重新排序成本低得多。

它是优先级驱动算法的骨架，也是采访中"k 个最大/最小"问题的常见工具。

操作	时间
peek min/max	O(1)
push (insert)	O(log n)
pop (extract)	O(log n)
build heap from n items	O(n)