Data Structures · Cluster
Heaps and Priority Queues
Partial orders and efficient extraction.
- 01 Array Layout and the Sift Invariant in Binary Heaps How a complete binary tree maps onto a flat array with no pointers, why the heap property is a partial order, and what sift-up and sift-down actually cost.
- 02 Bottom-Up Heap Construction in Linear Time Why sifting down from the middle of the array builds a heap in O(n) rather than O(n log n), and how the node-counting argument bounds the total work.
- 03 Indexed Binary Heaps and the Cost of Decrease-Key Why changing a key in place needs a handle from element to heap slot, how the position map is maintained through sifts, and what lazy deletion trades away.
- 04 d-Ary Heaps and How Branching Factor Changes Cost Trading comparisons per level against levels per sift, why four children often beats two on real hardware, and where the arithmetic stops fitting in a register.
- 05 Leftist and Skew Heaps: Merging in Logarithmic Time How a rank stored per node bounds the right spine, why skew heaps drop the rank and still amortise to logarithmic merge, and what the recursion costs.
- 06 Binomial Queues and the Carry Chain of Merges Why storing trees of size 2^k makes merge look like binary addition, how extract-min decomposes the forest, and what the lazy structure costs in pointers.
- 07 Pairing Heaps and the Two-Pass Merge How a self-adjusting heap replaces rank bookkeeping with a left-to-right then right-to-left merge, why melding is constant time, and what the amortised bounds actually are.
- 08 Fibonacci Heaps and the Amortised Case for Decrease-Key How deferred consolidation makes meld and decrease-key constant amortised, what the potential function measures, and why the theoretical win rarely survives contact with memory.
- 09 Min-Max Heaps and Double-Ended Extraction How alternating min and max levels let one array serve both ends of a priority queue, why sift-down needs two directions, and what the layout gives up.
- 10 Monotone Integer Keys: Bucket Queues and Radix Heaps When extracted keys never decrease, an array of buckets beats comparison-based heaps; how circular bucket arrays and radix heaps exploit integer bounds.