Heaps, Union-Find and Advanced Structures
Heaps give O(1) access to one extreme and O(log n) updates; union-find, skip lists and Bloom filters solve connectivity, ordered sets and membership with clever trade-offs.
Key points
- 1
In a 0-indexed array heap, children of p are 2p+1 and 2p+2 and the parent of i is (i-1)//2. Only the root is guaranteed to be the minimum.
- 2
Bottom-up heapify is O(n), not O(n log n): most nodes sit near the bottom and sift down only a short way.
- 3
Python's heapq is a min-heap: negate keys for a max-heap, and add a counter as a tie-breaker so payloads are never compared.
- 4
Top-k largest: keep a min-heap of size k, giving O(n log k) time and O(k) space. Merging k sorted lists with a heap is O(N log k).
- 5
Running median: a max-heap for the lower half and a min-heap for the upper half, rebalanced so their sizes differ by at most one.
- 6
Union-find with path compression and union by rank or size costs O(m α(n)) for m operations; always link roots, never raw nodes.
- 7
Skip lists give expected O(log n) ordered operations; Bloom filters give no false negatives and a tunable false-positive rate (≈1% at 10 bits per item).
Common traps
heapreplace always keeps the new item, even when it's smaller than the root; use heappushpop for a bounded top-k.
heapq has no decrease-key: push a new entry and skip stale ones when they're popped (lazy deletion).
Clearing bits to delete from a plain Bloom filter can cause false negatives; use a counting Bloom filter instead.
Read the source
Test yourself on Heaps, Union-Find and Advanced Structures
Ten questions, with the answer and explanation after each one.