Heaps and Priority Queues for Coding Interviews: From Implementation to Top-K Problems

A priority queue is a container that always returns its smallest (or largest) item next. A heap is the array-backed tree that implements it. Push and pop are logarithmic, about 20 steps for a million items.

Any problem that repeatedly asks for the current smallest item is a heap problem. Sorting the whole set again after every change would cost far more.

This guide covers the array layout, push and pop, their costs, Python's heapq, and the five problem families.

How a heap stores a tree in an array

A binary heap is a complete binary tree stored in a plain array. A binary tree is a tree where each node has at most two children. Complete means every level is full except possibly the last, which is filled from the left.

With no gaps, the tree needs no pointers, and each node's position follows from its index.

For the node at index i, the children are at 2i + 1 and 2i + 2. The parent is at (i - 1) // 2, where // is integer division.

Take the array [1, 3, 2, 7, 4]. Index 0 is 1, and its children are index 1 (3) and index 2 (2). The children of index 1 are index 3 (7) and index 4 (4).

One more rule makes it a min-heap: every parent is less than or equal to both of its children. So the smallest item is always at index 0, called the root. A max-heap reverses the rule, so the largest item is at the root.

Nothing else is ordered. The tree basics behind this layout are in mastering tree and graph data structures for coding interviews.

Sift-up on push and sift-down on pop

Sift-up repairs the heap rule after a push, which adds an item. Sift-down repairs it after a pop, which removes the root.

Push. Append the new item at the end of the array. Then swap it with its parent while it is smaller.

This is sift-up. It stops at the root or at a parent that is already smaller. The block below is a min-heap push on a Python list.

def sift_up(heap, i):
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] >= heap[parent]:
            return
        heap[i], heap[parent] = heap[parent], heap[i]
        i = parent

def push(heap, item):
    heap.append(item)
    sift_up(heap, len(heap) - 1)

The item moves up one level per swap, so the cost is the number of levels.

Pop. The answer is the root, but removing index 0 would leave a gap. So move the last item into index 0 and remove the last position.

Then swap the new root with its smaller child while that child is smaller. This is sift-down, and it stops when neither child is smaller.

The block below is the matching pop. It assumes the heap is not empty.

def sift_down(heap, i):
    n = len(heap)
    while True:
        left, right, smallest = 2 * i + 1, 2 * i + 2, i
        if left < n and heap[left] < heap[smallest]:
            smallest = left
        if right < n and heap[right] < heap[smallest]:
            smallest = right
        if smallest == i:
            return
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest

def pop(heap):
    heap[0], heap[-1] = heap[-1], heap[0]
    top = heap.pop()
    sift_down(heap, 0)
    return top

Choosing the smaller child matters. Swapping with the larger child would put a large value above a smaller one and break the rule.

What each heap operation costs

Logarithmic cost means the step count grows with the number of levels, not the number of items. Doubling the items adds one level. So a billion items means about 30 steps.

Peek means reading the root without removing it. Pushing n items one at a time costs n log n. Heapify builds the heap in linear time instead.

It runs sift-down from the last parent back to the root. Most nodes are on the lowest levels, so they move little. The notation for these costs is explained in Big-O algorithm complexity.

Python heapq and Java PriorityQueue

Python's heapq module runs heap operations on a plain list. It is a min-heap only, with no max-heap option. The block below shows the calls used most in interviews.

import heapq

nums = [5, 1, 4, 2, 3]
heapq.heapify(nums)               # linear time; nums[0] is now 1
heapq.heappush(nums, 0)
smallest = heapq.heappop(nums)    # 0

max_heap = []                     # max-heap: store negated values
for x in [5, 1, 4]:
    heapq.heappush(max_heap, -x)
largest = -heapq.heappop(max_heap)   # 5

tasks = [(2, 0, "write"), (1, 1, "read"), (2, 2, "test")]
heapq.heapify(tasks)              # (priority, counter, name)
first = heapq.heappop(tasks)[2]   # "read"

For a max-heap, push the negated value and negate it again after the pop. Other options, including a wrapper class, are in a max-heap implementation in Python.

Tuples compare element by element, so (priority, counter, item) orders by priority first. The counter is a tie-breaker: a second value that decides the order when priorities are equal. Without it, Python compares the third element, and a dictionary there raises a TypeError.

heapq.nlargest(k, items) and heapq.nsmallest(k, items) return the k largest or smallest values as a sorted list. Both accept a key function, like sorted does.

Java's PriorityQueue is also a min-heap by default. Passing a comparator, an object that compares two items, to the constructor changes the order.

Grokking Data Structures for Coding Interviews teaches heaps and the other core structures with runnable code.

Top-k elements

The question gives n items and asks for the k largest. A full sort costs n log n. A heap of size k costs n log k.

The heap is a min-heap, even though the question asks for the largest items. Push each item, and when the size exceeds k, pop once. The pop removes the smallest of the k + 1 items, which cannot be in the answer.

After one pass, the heap contains the k largest, and its root is the k-th largest.

import heapq

def k_largest(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap    # the k largest, in heap order, not sorted

The same loop solves Top K Frequent Elements with (count, value) tuples. K Closest Points to Origin asks for the smallest distances, so its heap is a max-heap of size k.

K-way merge

The question gives k sorted lists with n items in total and asks for one sorted list. Concatenating and sorting costs n log n. A heap with one item per list costs n log k.

The heap stores the head of each list, the smallest item not yet taken. Pop the smallest head, output it, and push the next item from the same list. Each item is pushed and popped once, and the heap never has more than k entries.

import heapq

def merge_k(lists):
    heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
    heapq.heapify(heap)
    out = []
    while heap:
        value, i, j = heapq.heappop(heap)
        out.append(value)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
    return out

Each tuple stores the value, the list index, and the position inside that list. The list index also serves as the tie-breaker.

Two heaps for a running median

The question gives numbers one at a time and asks for the median after each one. The median is the middle value of a sorted list, or the average of the middle two. Two heaps make it log n per number.

Keep the smaller half in a max-heap called low and the larger half in a min-heap called high. The median is the root of low, or the average of both roots when the halves are equal. The sizes may differ by at most one, and low keeps the extra item.

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []     # max-heap, values negated
        self.high = []    # min-heap

    def add(self, x):
        heapq.heappush(self.low, -x)
        heapq.heappush(self.high, -heapq.heappop(self.low))
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def median(self):
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

Every new number is pushed into low first. Then the largest value in low moves to high. That guarantees every value in low is less than or equal to every value in high.

The size check then moves one value back if high has become larger.

Scheduling problems

Meeting Rooms II gives meeting start and end times and asks for the minimum number of rooms. Sort the meetings by start time. Keep a min-heap of the end times of meetings still in progress.

For each meeting, read the earliest end time in the heap. If it is at or before the new start time, pop it, because that room is free.

Then push the new end time. The maximum heap size during the pass is the answer, and the method costs n log n.

Task Scheduler gives task types and a cooldown, the required gap between two runs of the same type. Count each type and push the counts into a max-heap.

In each round, pop up to cooldown + 1 tasks and run each once. Push each nonzero count into the heap again. The max-heap always returns the type with the most remaining runs.

Running that type first produces the fewest idle slots, the time units where no task can run.

Shortest paths with Dijkstra

Dijkstra's algorithm finds the shortest distance from one source node to every other node. It requires that no edge weight is negative.

It keeps a min-heap of (distance, node) pairs and pops the closest node that is not yet settled. Settled means its shortest distance is final.

For each neighbor of the popped node, it checks whether the path through this node is shorter. If so, it pushes a new (distance, neighbor) pair instead of updating the old one.

When the old pair is popped later, it is larger than the best known distance, so it is skipped. This is called lazy deletion. With V nodes and E edges, the cost is (V + E) log V.

When a heap is the wrong tool

Every item in sorted order. Popping n items from a heap costs n log n, the same as sorting. Sorting is simpler and usually faster.

A single k-th element with all data in memory. Quickselect finds it in linear time on average. It partitions the list around one chosen value and recurses into one part only.

A heap is better when items arrive over time or memory is limited to k items.

The maximum of every sliding window. A monotonic deque is a double-ended queue whose values are kept in decreasing order. Each element is added and removed once, so the whole pass is linear.

A heap costs n log n here and needs lazy deletion for values no longer in the window.

Heap problem families in one table

Here n is the item count, k the number kept or merged, and V and E the nodes and edges of a graph.

These families are five of the patterns in LeetCode coding patterns. Naming the family first is the fastest way to choose the heap kind and size.

Common heap mistakes

A max-heap for the k largest. The root of a size-k heap must be the item to discard next. For the k largest, that item is the smallest, so the heap is a min-heap.

No tie-breaker in the tuples. Equal priorities make Python compare the next element, and a dictionary there raises a TypeError. Put an integer counter in the second position.

Changing an item already in the heap. The heap rule was checked when the item was pushed, and never again. Editing its priority in place breaks the rule, and no error is raised.

Push a new entry instead, and skip the stale one when it is popped.

Treating the heap list as sorted. After the top-k loop, the list is in heap order, not sorted order. Call sorted on the result if the question asks for order.

Frequently asked questions

What is the difference between a heap and a priority queue? A priority queue is the interface: push an item, pop the smallest or largest. A heap is the data structure that usually implements it, with logarithmic push and pop.

Is Python heapq a min-heap or a max-heap? heapq is a min-heap only. For a max-heap, push the negated value and negate it again after the pop. For objects, push a tuple of (negated key, counter, object).

When should I use a heap instead of sorting? Use a heap when you need only the k smallest or largest items. It is also right when items arrive one at a time. Use a sort when you need every item in order.

How do you change the priority of an item in a heap? Push a new entry with the new priority and mark the old one stale. When the old entry is popped, skip it. This is called lazy deletion.

Which interview problems use two heaps? Find Median from Data Stream, Sliding Window Median, and IPO. Each keeps a max-heap for the lower half and a min-heap for the upper half.

Heaps are one pattern family among many. Grokking the Coding Interview teaches top-k, k-way merge, and two heaps as separate patterns, with runnable solutions.

Related reading

• What to use for a max-heap implementation in Python
• Mastering tree and graph data structures for coding interviews
• Big-O algorithm complexity
• LeetCode coding patterns
• Python cheat sheet for coding interviews