Sign in to watch this lesson
Advanced - Data Structures and Range Queries Ā· 5:13
Randomized (Meldable) Heap
A randomized meldable heap is a binary tree in heap order where every operation is one merge: push merges in a single node, pop merges the root's two children, deleting a known node merges its children in its place, and melding two heaps is one merge. Merge keeps the smaller root on top, flips a fair coin to swap that root's children, and recurses into the left child; the expected path length is at most log(n + 1), and long paths are exponentially rare. That makes heap melding O(log n), which binary heaps can't do, and it powers bottom-up merging in tree problems and slope trick.
You will learn
- Implement merge for a randomized meldable heap (smaller root on top, coin-flip swap, recurse left) and express push, pop, erase and meld through it
- Explain why the expected merge path is at most log(n + 1) and why long paths are rare
- Use melding to combine heaps bottom-up in a tree, trimming each heap to the k items that matter
- Avoid the practical pitfalls: weak random sources, per-node allocation and forgetting that duplicates are kept