Priority Queue

Pull the next task in priority order from a stream of millions, and a sorted array gives you `O(1)` extract but `O(n)` insert; a sorted linked list flips the costs but stays linear; a balanced BST hits `O(log n)` for both but with substantial pointer overhead. A **Heap** quietly outperforms all three for this exact workload by storing a complete binary tree in a flat array and keeping just the min (or max) at the root. This lesson covers the heap property, the parent-and-child index formulas (`parent = (i-1)/2`, `left = 2i+1`, `right = 2i+2`) that let array indices encode tree structure with no pointers, sift-up and sift-down for `O(log n)` insert and extract, and the linear-time `heapify` build. You will see how this maps onto the priority queue abstraction and onto interview staples such as top-K elements, K-th largest, merge K sorted lists, and the streaming median with two heaps; on the systems side, the same structure powers Dijkstra and Prim. In **Trees: Binary Tree Fundamentals**, you saw what a complete binary tree is and how to traverse one; the heap reuses that exact shape but stores it implicitly. **Arrays & Strings** is what makes the implicit storage cheap: a flat array gives `O(1)` parent and child access through arithmetic, with no allocations per node. Next, **Binary Search Tree (BST)** trades the heap's partial ordering for a full ordering invariant, unlocking sorted iteration and key-based search at the cost of needing actual pointers.

For a set of 32-bit integers, balanced BSTs answer successor and predecessor queries in `log_2(2^32) = 32` comparisons, and hash tables cannot answer those queries at all. A **Van Emde Boas (vEB) tree** answers them in `log_2(log_2(2^32)) = 5`, by recursively halving the bit-length of the universe at each level rather than halving the number of elements. That doubly-logarithmic bound is one of the most striking results in data structure theory. This lesson covers the recursive vEB structure (an integer universe `[0, u-1]` is split into `sqrt(u)` clusters of size `sqrt(u)` plus a summary structure over which clusters are non-empty, applied recursively), the explicit `min` and `max` fields that short-circuit the recursion to a single level when possible, the `O(log log u)` analysis for insert, delete, member, successor, predecessor, min, and max, and the `O(u)` space cost that makes vEB trees practical only for moderate universes. In **Binary Search Tree (BST)**, the height (and thus the operation cost) was governed by the number of stored keys; the vEB tree is governed instead by the size of the integer universe, a fundamentally different parameter. **Heaps & Priority Queue** introduced fast min and max access through a structural invariant; vEB trees push that idea further by also providing fast `successor` and `predecessor` over the same set. With Van Emde Boas, the data structures track is complete; the algorithms track is where these structures come alive in real problem solving.