Max Heap

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.