堆与优先队列
What Is a Heap?
A heap is a complete binary tree where every parent satisfies the heap property - either always smaller (min-heap) or always larger (max-heap) than its children. "Complete" means every level is full except possibly the last, which fills left to right.
1 Min-heap
/ \
3 5
/ \
7 4
Because it's complete, we store it in a flat array - no pointers needed. For index i: left child = 2i + 1, right child = 2i + 2, parent = (i - 1) // 2.
Min-Heap vs Max-Heap
| Property | Min-Heap | Max-Heap | |----------|----------|----------| | Root | Smallest element | Largest element | | Parent ≤ Children? | ✅ Yes | ❌ No (≥) | | Extract gives | Minimum | Maximum |
Python's heapq is a min-heap by default. For a max-heap, negate values on insert and negate again on extract.
Insert and Extract - Step by Step
Insert - push to end, then bubble up (swap with parent while smaller):
import heapq
h = [1, 3, 5, 7]
heapq.heappush(h, 2) # h becomes [1, 2, 5, 7, 3]
Extract min - swap root with last element, pop last, then sift down (swap with smaller child):
smallest = heapq.heappop(h) # returns 1
Both operations run in O(log n) because the tree height is log n.
Heapify - Building a Heap in O(n)
Calling heapq.heapify(arr) converts a list into a heap in O(n), not O(n log n). It works bottom-up, sifting down each non-leaf node. This is one of the most surprising complexity results in CS.
Discussion
Sign in to join the discussion