Heap vs Priority Queue

A heap is a data structure: a complete binary tree arranged so that every parent is no greater than its children, which makes the smallest element sit at the root. A priority queue is an interface: a collection where you can insert items with a priority and always remove the one with the highest priority.

The priority queue is usually implemented with a heap, but the two words are used loosely and interchangeably in industry. When someone says use a priority queue in an interview, they almost always mean use a heap underneath, because the heap gives you logarithmic insertion and removal of the extreme element.

import heapq

tasks = [(3, "write docs"), (1, "fix bug"), (2, "review pull request")]
heapq.heapify(tasks)
print(tasks[0])

The output is the tuple one and fix bug, because heapify arranges the list so the smallest tuple is at index zero, and the tuple comparison orders by the first element, which is the priority.

The mechanism is the heap invariant combined with the complete tree layout. Because the tree is complete, the children of the node at index i are at two i plus one and two i plus two, so the structure can live in a plain array with no pointers. The invariant lets the smallest element be found in constant time and the next smallest be restored in logarithmic time after a removal.

The trade-off to name is that a heap only gives you the extreme element cheaply. Finding the fifth smallest is linear, and removing an arbitrary element is linear too, because the heap has no ordering among the non-root elements. If you need more than the extreme, a balanced tree or a sorted structure is the better tool, and that is the point to make when choosing a data structure in a design discussion.

Python's heapq module works on a plain list. You push with heappush, pop with heappop, and you can look at the smallest element with the index zero access.

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
print(heap)
print(heapq.heappop(heap))
print(heap)

The outputs are the list 2, 5, 8, then the number 2, and then the list 5, 8. The first list is already in heap order, though it is not fully sorted, and the pop removes the smallest element and restores the invariant.

The mechanism is that heappush appends the value to the end of the list and then sifts it up towards the root, swapping with its parent whenever the parent is larger. The sift stops as soon as the parent is smaller, so the number of swaps is bounded by the height of the tree, which is logarithmic.

The trade-off to name is that Python's heap is a min heap, so the smallest element comes out first. Getting the largest element out means either negating the values, which changes the meaning of the data, or using a different structure such as the sortedcontainers module, which is not in the standard library. There is also the point that heappush and heappop are separate operations, so a push followed by a pop costs two logarithmic walks, whereas heapreplace does both in one and is the right call when you know the incoming value will displace the root.

Store the negated values. Because a min heap always surfaces the smallest stored value, storing the negative of each value makes the largest original value the smallest stored one.

import heapq


class MaxHeap:
    def __init__(self):
        self.items = []

    def push(self, value):
        heapq.heappush(self.items, -value)

    def pop(self):
        return -heapq.heappop(self.items)

    def peek(self):
        return -self.items[0]


heap = MaxHeap()
heap.push(3)
heap.push(7)
heap.push(1)
print(heap.pop())
print(heap.peek())

The outputs are 7 and 3. The largest value pushed was 7, and after removing it the largest remaining value is 3.

The mechanism is that negating reverses the comparison order. The negated heap holds minus three, minus seven and minus one, and its smallest element is minus seven, which corresponds to the original value 7. Every read and write has to apply the negation, and forgetting to negate on the way out is the classic bug.

The trade-off to name is that negation only works for numbers. As soon as you need arbitrary objects with a comparison key, you have to wrap them in tuples with the negated priority as the first element, which adds an allocation per item and makes the comparison slightly more expensive. The other alternative is to write your own heap, which the last page of this group does, and that is worth doing once so you understand the invariant even if you use the library afterwards.