Heaps and priority queues

A heap always has the smallest (or largest) item ready for you, and it doesn't have to keep everything sorted to do it. It's the usual way to build a priority queue.

It's stored as an array but you treat it like a tree. Adding or removing something moves it up or down one path, so it takes O(log n). If you want the k largest items, keep a min-heap of size k and keep throwing out the smallest:

import heapq


def k_largest(numbers, k):
    heap = []
    for number in numbers:
        heapq.heappush(heap, number)
        if len(heap) > k:
            heapq.heappop(heap)  # Drop the smallest of the k + 1.
    return sorted(heap, reverse=True)

Python's heapq only does min-heaps. If you need a max-heap, the usual trick is to store negative numbers.

• Look out for "top k," "next earliest," or merging sorted lists.
• Be able to explain why a heap of size k gets you O(n log k) and not O(n log n).
• Heaps are also what makes Dijkstra fast, and they're all over scheduling problems.

Merging k sorted lists

You have k sorted lists of numbers, with n numbers in total. Merge them into one sorted list.

1. Putting everything together and sorting is O(n log n), and it ignores the fact that each list is already sorted.
2. At any moment the next number in the output is the smallest of the k list heads. So you only need the minimum of k things, over and over. That's a heap.
3. Push the first item of each list as (value, list index, position).
4. Pop the smallest, add it to the output, and push the next item from the same list if there is one.
5. The heap never has more than k items, so each push and pop is O(log k). With n items in total, that's O(n log k).
6. Include the list index in the tuple. If two values are equal, Python compares the next field, and you don't want it trying to compare things that can't be compared.

Things interviewers tend to ask once you've brought this up.

How do you keep a running median?

Two heaps: a max-heap for the smaller half and a min-heap for the larger half. Keep their sizes within one of each other, and the median is at the top of one or both.

How many meeting rooms do you need?

Sort meetings by start time and keep a min-heap of end times. If the earliest end is before the next start, reuse that room. The biggest the heap gets is the answer.

How do you remove an item that isn't at the top?

The usual trick is lazy deletion. Mark it removed in a set, and skip it when it reaches the top.

Can you find the top k without a heap?

Quickselect finds the kth largest in O(n) on average, but it rearranges the input and its worst case is O(n²). If k is small or data keeps coming, a heap is the safer pick.

• Using a max-heap of everything for the top k, which is O(n log n), instead of a min-heap of size k.
• Forgetting Python's heapq is a min-heap.
• Pushing tuples with values that can't be compared when there's a tie.
• Thinking a heap's array is sorted. Only the top is guaranteed.
• Searching a heap for an arbitrary value and calling it O(log n).

• Graph traversal and shortest pathsBFS, DFS and Dijkstra, and when to use each.
• Binary searchCut the search in half, even when you're searching for an answer.
• Dynamic programmingSolve each subproblem once and reuse the answer.