Heaps and Priority Queues Explained With Examples

Quick Answer

A heap is a complete binary tree where every parent is smaller than its children in a min-heap, or larger in a max-heap. It gives O(1) access to the minimum or maximum and O(log n) insertion and removal, without the cost of keeping everything sorted. It is stored in a plain array using index arithmetic rather than nodes and pointers. A priority queue is the abstract idea; a heap is the usual implementation.

What a Heap Is

A heap satisfies two properties.

The heap property: in a min-heap, every parent is less than or equal to its children. In a max-heap, greater than or equal.

Completeness: every level is full except possibly the last, which fills left to right.

Min-heap:
            1
          /   \
         3     5
        / \   /
       4   8 7

Notice what a heap does not guarantee: it is not sorted. The only thing you know is that the root is the smallest — the relationship between siblings is unspecified. That weaker guarantee is exactly why heap operations are cheaper than maintaining a sorted list.

Because it is complete, a heap is stored in an array with no pointers at all. The tree structure is implied by index arithmetic:

Array:  [1, 3, 5, 4, 8, 7]
Index:   0  1  2  3  4  5

For index i:
  parent      = (i - 1) // 2
  left child  = 2i + 1
  right child = 2i + 2

That layout is why heaps are fast in practice as well as in theory — contiguous memory means good cache behaviour, unlike a pointer-based tree.

How Insert and Extract Work

Insert — O(log n). Add the element at the end, then "bubble up" while it is smaller than its parent.

Insert 2 into [1, 3, 5, 4, 8, 7]

Append:     [1, 3, 5, 4, 8, 7, 2]
2 < parent 5 → swap:  [1, 3, 2, 4, 8, 7, 5]
2 > parent 1 → stop

At most one swap per level, and the height is log n.

Extract minimum — O(log n). Take the root, move the last element to the root, then "sink down" by swapping with the smaller child until the property holds.

Moving the last element to the root — rather than promoting a child — is what preserves completeness, which is the detail people get wrong when implementing it.

Peek — O(1). The minimum is simply index 0.

Building a heap from an array — O(n), not O(n log n). This surprises people. Inserting n elements one at a time is O(n log n), but heapifying in place from the middle backwards is O(n), because most nodes are near the bottom and sink only a short distance.

import heapq
nums = [5, 3, 8, 1, 9]
heapq.heapify(nums)      # O(n), in place

Using Heaps in Practice

Python's heapq is a min-heap and operates on a plain list.

import heapq

h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 3)

heapq.heappop(h)     # 1  — smallest
h[0]                 # peek without removing
heapq.heappushpop(h, 4)   # push then pop, cheaper than doing both

There is no max-heap. The standard workaround is to negate the values:

heapq.heappush(h, -value)
largest = -heapq.heappop(h)

For tuples, the heap compares the first element, then the second, and so on — which is how you attach a priority to arbitrary data:

heapq.heappush(h, (priority, task))

Be careful: if two priorities tie, Python compares the second element, and if that is an object with no ordering defined it raises a TypeError. The usual fix is a counter as a tiebreaker: (priority, count, task).

In Java use PriorityQueue, which is a min-heap by default and takes a comparator for max behaviour. In C++, std::priority_queue is a max-heap by default — the opposite of Python, which catches people switching languages.

The Top-K Pattern

This is the reason heaps appear so often in interviews. "Find the k largest", "k most frequent", "k closest points" all share one solution.

The naive approach sorts everything — O(n log n) — and then takes k. The heap approach is O(n log k), which is much better when k is small relative to n.

The counter-intuitive part: to find the k largest, use a min-heap.

import heapq

def k_largest(nums, k):
    h = []
    for n in nums:
        heapq.heappush(h, n)
        if len(h) > k:
            heapq.heappop(h)      # remove the smallest of the k+1
    return h                      # the k largest remain

The reasoning: keep a heap of exactly k elements. The root is the smallest of your current best k, so it is the one to evict when a better candidate arrives. A max-heap would let you remove the largest, which is the opposite of what you want.

This also handles a stream of unknown length, where sorting is impossible because you never see all the data at once.

Related uses worth knowing: merging k sorted lists by pushing the head of each and repeatedly taking the minimum; finding a running median with two heaps, a max-heap for the lower half and a min-heap for the upper; and Dijkstra's algorithm, which is breadth-first search with a priority queue so the cheapest frontier node is expanded first.

When a Heap Is the Wrong Choice

Heaps are narrow tools, and knowing the boundary is part of a good answer.

• You need everything sorted. Just sort — O(n log n) once beats n extractions at O(log n) each with worse constants.
• You need to search for an arbitrary element. A heap has no ordering between siblings, so finding a specific value is O(n). Use a hash set or a balanced tree.
• You need the kth element repeatedly with updates. A balanced BST or an order-statistic tree handles that better.
• k is close to n. Then O(n log k) approaches O(n log n) and sorting is simpler.

A detail interviewers probe: a heap gives O(1) access to the minimum only. Finding the second smallest is not O(1) — it is one of the root's two children, but determining which requires a comparison, and the third smallest is genuinely awkward. If the question needs ordered access beyond the extreme, a heap may be the wrong structure.

Heapsort is worth mentioning as an application: build a heap in O(n), then extract n times at O(log n) each, giving O(n log n) with O(1) extra space. It is not stable, and in practice quicksort is usually faster, which is why heapsort mostly appears as the fallback inside hybrid sorts.

Frequently Asked Questions