Heaps & Priority Queues

A heap is a complete binary tree stored in an array that maintains the heap property: min-heap has the smallest element always at the root (index 0). This enables O(1) peek and O(log n) push/pop. The mental model: a heap is a half-sorted structure — you only care about the min (or max), not full sorted order. Three canonical patterns: (1) Top-K problems using a heap of size k; (2) merge K sorted sequences with a heap tracking the current minimum; (3) two-heap technique for maintaining a running median. What Are Arrays? An array is a contiguous block of memory storing elements of the same type. Each element is accessed by its index in O(1) time. Arrays are the most fundamental data structure — almost every interview starts here. Why arrays matter in interviews: They test your ability to manipulate indices and pointers Many problems reduce to array manipulation Understanding memory layout helps with optimization Key patterns: Two pointers (opposite ends, same direction) Sliding window (variable or fixed size) Prefix sums for range queries In-place modification to avoid extra space Complexity cheat sheet: Time O(1) O(n) O(log n) O(1) amortized O(n) Heaps & Priority Queues A heap is a complete binary tree where parent ≤ children (min-heap) or parent ≥ children (max-heap). It gives O(log n) insert and O(1) peek at min/max. Top-K Pattern Merge K Sorted Lists Median of Data Stream Key Problems #215 Kth Largest, #23 Merge K Sorted Lists, #295 Find Median #373 K Pairs with Smallest Sums, #767 Reorganize String Interview Tip "For any top-K or streaming problem, think heap first. A min-heap of size K gives O(n log K) which beats sorting at O(n log n)." Java Implementation