Heaps and Priority Queues: The Data Structure You Use More Than You Think

A priority queue is an abstract idea: a collection where you can insert elements and always extract the one with the highest (or lowest) priority. A heap is how you actually build one.

You could implement a priority queue with a sorted array (O(1) extract, O(n) insert) or an unsorted array (O(1) insert, O(n) extract). A heap gives you O(log n) for both, which is the sweet spot.

The Heap Structure

A binary heap is a complete binary tree where every parent satisfies the heap property:

• Min-heap: parent <= both children


• Max-heap: parent >= both children

"Complete binary tree" means every level is fully filled except possibly the last, which is filled left to right. This property is what lets us use an array instead of actual tree nodes.

Array Representation

This is the clever part. Store the heap as a flat array where:

• Root is at index 0


• For a node at index i:

- Left child: 2*i + 1
- Right child: 2*i + 2
- Parent: (i - 1) // 2

No pointers, no node objects, no wasted memory. Just an array. The complete tree property guarantees no gaps.

Array: [1, 3, 2, 7, 6, 5, 4]

Tree view:
        1
       / \
      3   2
     / \ / \
    7  6 5  4

Index 0 holds 1 (root). Index 1 holds 3 (left child of root). Index 2 holds 2 (right child of root). And so on. The formulas just work.

Insert (Bubble Up)

Add the new element at the end of the array (next available position in the last level). Then "bubble up": compare with parent, swap if the heap property is violated, repeat until it's satisfied or you reach the root.

def insert(self, val):
    self.heap.append(val)
    i = len(self.heap) - 1
    while i > 0:
        parent = (i - 1) // 2
        if self.heap[i] < self.heap[parent]:  # min-heap
            self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
            i = parent
        else:
            break

Worst case: the new element bubbles all the way to the root. That's the height of the tree, which is O(log n).

Extract Min/Max (Bubble Down)

Remove the root (the min or max element). Move the last element in the array to the root position. Then "bubble down": compare with both children, swap with the smaller child (min-heap) or larger child (max-heap), repeat.

def extract_min(self):
    if not self.heap:
        return None
    min_val = self.heap[0]
    self.heap[0] = self.heap[-1]
    self.heap.pop()
    i = 0
    while True:
        left = 2 * i + 1
        right = 2 * i + 2
        smallest = i
        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right
        if smallest != i:
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            i = smallest
        else:
            break
    return min_val

Again O(log n) — at most you traverse the height of the tree.

Heapify: Building a Heap in O(n)

If you have an unsorted array and want to turn it into a heap, you might think it's O(n log n) — insert each element one by one. But there's a better way.

Start from the last non-leaf node and bubble down each one. Because most nodes are near the bottom (and bubble down at most a small distance), the total work is O(n), not O(n log n). The math works out because of how the geometric series sums.

This is relevant when you need to heapify a collection at the start of a problem rather than inserting elements one at a time.

Where Priority Queues Show Up

Dijkstra's shortest path — the min-heap holds (distance, node) pairs. You always process the closest unvisited node. Without a heap, Dijkstra's degrades from O(E log V) to O(V^2). K largest/smallest elements — maintain a min-heap of size K. For each new element, if it's larger than the heap's minimum, replace the minimum. At the end, the heap contains the K largest elements. O(n log K) instead of O(n log n) for sorting. Merge K sorted lists — push the head of each list into a min-heap. Extract the minimum, advance that list's pointer, push the next element. The heap always gives you the global minimum across all K lists. O(N log K) where N is total elements. Task scheduling — process tasks by priority or deadline. Operating system schedulers, job queues, event-driven simulations. Anywhere "handle the most urgent thing next" is the strategy. Median maintenance — keep a max-heap for the lower half and a min-heap for the upper half. Balance their sizes. The median is always at one of the two heap tops. O(log n) per insertion with O(1) median query.

Language Built-Ins

Python has heapq (min-heap only — negate values for max-heap). Java has PriorityQueue. C++ has priority_queue (max-heap by default). JavaScript... doesn't have one in the standard library, which is why you'll see people implementing heaps from scratch in JS interviews.

Know your language's heap API. In interviews, nobody expects you to implement a heap from scratch unless that's literally the question. Use the built-in and focus on the actual problem.

The Mental Model

Whenever a problem says "repeatedly find the minimum/maximum" or "process elements in priority order" or "find the K-th something," a heap should be your first thought. It's the data structure for "I need fast access to the extreme element, and the collection keeps changing."

Practice heap-based problems on CodeUp — problems like K closest points, top K frequent elements, and merge intervals become much more approachable once the heap pattern clicks.