A heap is a specialized binary tree that gives you the minimum (or maximum) element in O(1) time, with O(log n) inserts and removals. That single guarantee - fast access to the smallest or largest item without keeping the entire collection sorted - is what makes heaps the right answer for "top K", "running median", and "merge K sorted lists" problems.

The Heap Property

A min-heap is a complete binary tree in which every node is less than or equal to its children. The smallest value in the heap is therefore always at the root. A max-heap flips the comparison: every node is greater than or equal to its children, so the largest value sits at the root. The structure does not promise any ordering between siblings or between unrelated subtrees - only the parent-child relationship matters.

This relaxed invariant is the source of the heap's efficiency. A fully sorted structure costs O(n log n) to build and O(log n) per insert just to maintain order. A heap costs O(n) to build and O(log n) per insert because it only enforces the parent-child rule, not a global ordering.

Complete Binary Tree as an Array

A complete binary tree fills every level from left to right, leaving no gaps. This shape lets you store the heap in a flat array without any pointers. For a node at index i:

• The left child sits at index 2*i + 1
• The right child sits at index 2*i + 2
• The parent sits at index (i - 1) // 2

The completeness property guarantees that the array has no holes - every index from 0 to n-1 holds a valid element. This is what lets you compute parent and child positions with simple arithmetic instead of following pointers.

Why Not a Sorted Array

A sorted array also gives O(1) access to the minimum. The problem is insertion: adding a new element to a sorted array of size n costs O(n) because you must shift elements to keep the array sorted. A heap insert costs O(log n) because it only needs to fix one path from the new leaf up to the root.

Removing the minimum from a sorted array costs O(n) for the same reason - every other element shifts left. A heap remove-min also costs O(log n) by moving the last element to the root and sifting it down.

Heap vs Priority Queue

A priority queue is an abstract data type that supports "insert with priority" and "remove highest priority". A heap is the most common implementation of a priority queue, but they are not the same thing. You could implement a priority queue with a sorted list, an unsorted list, or a balanced BST - each with different performance trade-offs.

In Python, heapq operates on a regular list as a min-heap. In Java, PriorityQueue is a min-heap by default and accepts a comparator for custom orderings. In C++, priority_queue is a max-heap by default. Knowing these defaults saves debugging time when your "smallest" answer comes back as the largest.

The heap maintains its parent-child invariant through two operations: sift up (used during insertion) and sift down (used during removal). Both operations swap a misplaced element along a single root-to-leaf path, costing O(log n) per call because the height of a complete binary tree with n nodes is floor(log2 n).

Insertion via Sift Up

To insert a new element, append it to the end of the array (the next available leaf position). This preserves the complete tree shape but may violate the heap property if the new element is smaller than its parent. Walk up the tree, swapping the element with its parent as long as it is smaller. Stop when the parent is smaller (the heap property is restored) or you reach the root.

Inserting 2 into the heap [4, 5, 6, 9, 7]:

1. Append 2 at index 5. Heap is now [4, 5, 6, 9, 7, 2]. Parent of index 5 is index 2 (value 6).
2. 2 is less than 6, swap. Heap is [4, 5, 2, 9, 7, 6]. New index is 2, parent is index 0 (value 4).
3. 2 is less than 4, swap. Heap is [2, 5, 4, 9, 7, 6]. Index 0 is the root, stop.

Removal via Sift Down

To remove the minimum (the root), swap it with the last element in the array, then pop the last element to extract the original root. The element now at the root is almost certainly out of place, so sift it down: at each step, find the smaller of its two children. If that child is smaller than the current element, swap them. Stop when the element is smaller than both children (or has no children).

The crucial detail in sift down is comparing against the smaller child, not just the left child. Swapping with the larger child would create a new heap-property violation between the swapped value and the smaller sibling.

Watch stones smash together as the heap repeatedly extracts the two largest:

Building a Heap in O(n)

Inserting n elements one at a time costs O(n log n) because each insert is O(log n). But you can build a heap from an unsorted array in O(n) using a clever bottom-up approach: start at the last non-leaf node (index n//2 - 1) and call sift down on each index moving toward the root.

Why is this O(n) and not O(n log n)? Because most nodes are near the bottom of the tree, where sift down has very little work to do. Half the nodes are leaves (sift down does nothing). A quarter of nodes have height 1 (at most one swap). An eighth have height 2 (at most two swaps). The geometric series sums to O(n), not O(n log n).

Updating an Element

Heaps do not natively support efficient lookup or update of an arbitrary element - finding it costs O(n) because the structure is not sorted. If you need to update priorities (for example, in Dijkstra's algorithm), the standard trick is to push the updated value as a new entry and check whether the popped entry is still valid when you remove it. The "lazy deletion" pattern keeps the operations O(log n) at the cost of slightly more memory.

The "top K" pattern is the most common interview application of heaps. Whenever a problem asks for the K largest, K smallest, K most frequent, or K closest elements out of a stream or large array, the answer is almost always a heap of size K. The trick is choosing min-heap or max-heap correctly - and the choice is the opposite of what naive intuition suggests.

K Largest with a Min-Heap of Size K

To find the K largest elements out of n total, maintain a min-heap of size K. As you scan the array, push each element into the heap. When the heap exceeds size K, pop the smallest (the root). After processing all n elements, the heap holds exactly the K largest values.

Why a min-heap and not a max-heap? Because the root of a min-heap is the smallest of the K elements you currently hold - which is exactly the element you want to compare against new arrivals. If a new value is greater than the current minimum-of-the-top-K, it deserves a spot. If it is less, you can throw it away without further work.

A max-heap would do the opposite job: it gives O(1) access to the largest element, but to find the smallest of the top K (so you can decide whether to evict it), you would have to scan all K elements. That extra O(K) scan per insert would push the total cost from O(n log k) to O(nk).

Time Complexity: O(n log k)

The key insight is that the heap never grows beyond size K. Each heappush and heappop costs O(log K), not O(log n). Across n elements, the total cost is O(n log K). When K is much smaller than n (the typical case), this is dramatically faster than sorting the whole array (O(n log n)).

For finding the top 100 in a stream of 10 million, sorting takes roughly 10 million times log2(10 million) ≈ 230 million comparisons. The heap of size 100 takes 10 million times log2(100) ≈ 70 million comparisons - and uses 100x less memory because it never holds more than 100 elements.

Top K Frequent Elements

A natural extension is finding the K elements that appear most often in an array. Step 1: count frequencies in a hash map. Step 2: maintain a min-heap of size K, ordered by frequency. Step 3: walk through the hash map entries, pushing each (frequency, value) pair into the heap and popping when the heap exceeds K. The remaining heap contents are the K most frequent elements.

Total complexity is O(n log k): O(n) for counting, O(m log k) for the heap pass where m is the number of unique values (at most n).

See the min-heap of size K filter points by distance to the origin:

Practice: Kth Largest Element in a Stream

The streaming version of the top-K pattern: maintain a class that supports add(val) and returns the K-th largest element seen so far. The implementation is exactly a min-heap of size K - the root is always the K-th largest because there are exactly K-1 values larger than it in the heap.

Practice: Top K Frequent Elements

Combine a hash-map frequency count with the top-K min-heap pattern. Watch the heap key carefully - you are sorting by frequency, not by value, so the tuple (frequency, value) matters in that order.

Some problems need access to both the smallest and the largest of a partition simultaneously. The two-heap pattern solves this by maintaining a max-heap holding the smaller half of the data and a min-heap holding the larger half. The roots of both heaps give you the boundary elements in O(1) - and the running median problem falls out almost for free.

The Idea

Split the stream into two roughly equal halves. The lower half lives in a max-heap (so its largest element - the upper boundary of the lower half - is always at the root). The upper half lives in a min-heap (so its smallest element - the lower boundary of the upper half - is always at the root). The median is either the root of the larger heap (if the heaps are unequal in size) or the average of the two roots (if the heaps are equal).

1Max-heap (lower half):     Min-heap (upper half):
2      5                          7
3     / \                        / \
4    3   4                      8   9
5   /
6  1
7Stream so far: [1, 3, 4, 5, 7, 8, 9]
8Median = (5 + 7) / 2 = 6

Maintaining the Balance

Two invariants must hold after every insertion:

1. Ordering: every element in the max-heap is less than or equal to every element in the min-heap.
2. Size: the heaps differ in size by at most 1. By convention, allow the max-heap (lower half) to be one element larger.

To insert a new value, first decide which heap it belongs in. If the value is less than or equal to the root of the max-heap (the current upper bound of the lower half), push it to the max-heap. Otherwise, push it to the min-heap. Then rebalance: if the max-heap has more than one extra element, move its root to the min-heap; if the min-heap has more elements than the max-heap, move its root to the max-heap.

Watch the two heaps rebalance as each number arrives and the median updates in real time:

Step through the task scheduler picking the most frequent task at each slot:

Why This Works

The two-heap structure is essentially a partition of a sorted sequence into two halves, with O(1) access to the boundary on each side. Inserting a new value costs O(log n) (the heap operations) and finding the median costs O(1) (just look at the roots). Compare this to sorting the entire stream after every insert, which would be O(n log n) per insert.

The Python negation trick is necessary because heapq is a min-heap only. To simulate a max-heap, push the negation of every value and negate again when reading the root. Other languages (Java, C++) provide max-heap support directly via comparators.

When the Two-Heap Pattern Applies

Whenever you need to track a "boundary" or "split point" in dynamically changing data - running median, sliding window median, or any "k-th value out of an evolving set" - consider whether two heaps can hold the two sides of the boundary. The pattern generalizes beyond medians: you could use it to track the K-th smallest value at all times by sizing the lower heap to exactly K elements.

Practice: Find Median from Data Stream

The classic two-heap problem. Implement addNum(num) and findMedian() so that the median can always be queried in O(1) time after any number of insertions.