Heap & Priority Queue

A heap is the emergency-room triage nurse. No matter who walks through the door, the most urgent patient is always the next one seen, and slotting a new arrival into the right spot is quick. You never sort the entire waiting room - you just always know who's next.

Example: to keep the 3 largest numbers from a long stream, carry a small bag that holds only 3. Each time a new number arrives, if it's bigger than the smallest one in the bag, drop the smallest and add the newcomer. Whatever survives in the bag at the end is your top 3 - found without ever sorting the whole stream.

A heap is a complete binary tree packed into an array: for index i, children are at 2i+1 and 2i+2, parent at (i-1)/2. No pointers needed.

Key subtlety: building a heap from n items is O(n), not O(n log n), if you heapify in place bottom-up. Pushing them one at a time is O(n log n).

Java's PriorityQueue is a min-heap by default; pass a comparator for max-heap or custom priority. Python's heapq is always a min-heap and operates on a plain list — to get a max-heap, push negated values (or tuples with a negated key).

To find the k largest elements, keep a min-heap of size k (the counter-intuitive part). Push each element; if the heap exceeds size k, pop the smallest. What remains are the k largest, because the smallest of the top-k is exactly what you keep evicting. This is O(n log k) — better than sorting's O(n log n) when k ≪ n — and O(k) space.

To report the median as numbers stream in, keep two heaps: a max-heap for the lower half and a min-heap for the upper half. Keep their sizes balanced (differ by ≤ 1). The median is the top of the larger heap, or the average of both tops when sizes are equal. Each insert rebalances in O(log n). This is the canonical 'Find Median from Data Stream' solution.