What Is a Max-Heap? The Data Structure Behind Every Priority Queue

You have a million numbers arriving from a sensor. Every millisecond, you need the largest one. A sorted array works, right up until you do the math: sorting costs O(n log n) and you care about exactly one position. A plain array means scanning the whole thing each time. Congratulations, you've reinvented the world's saddest solution.

There's a better structure. The max-heap gives you the maximum in O(1) and updates in O(log n). Here's how it works, why it keeps appearing in interviews, and why Python decided to make it mildly annoying on purpose.

The Two Rules You Can't Violate

A max-heap is a complete binary tree where every parent node is greater than or equal to both of its children.

Complete binary tree means every level is fully filled except possibly the last, which fills left to right. No gaps, no skipping nodes in the middle. This regularity is what makes the whole structure work.

Max-heap property means the root always holds the largest element. Not just a large element. The largest. Every path from root to leaf is non-increasing. You go down and things only get smaller (or stay the same).

What the max-heap property does not guarantee: that the tree is sorted. The second-largest element could be anywhere in the first level. The heap promises each parent beats its children, not that siblings are ordered relative to each other. This partial ordering is deliberately lazy, and it's exactly what makes insertions and extractions fast. A fully sorted structure is expensive to maintain. The heap only promises what it absolutely has to.

One Tree, One Array

Here's the beautiful part. A complete binary tree maps directly onto a flat array. Given a node at index i in a 0-indexed array:

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

No pointers. No memory allocation per node. Just arithmetic on indices.

Index 0 holds 90 (root). Its children are at index 1 (50) and index 2 (70). Index 1's children are at index 3 (20) and 4 (30). The formulas work everywhere.

This is the core efficiency: no pointer overhead, contiguous memory, cache-friendly access. A linked binary tree burns extra memory on pointers and scatters nodes across the heap (the memory heap, not the data structure heap, which makes this paragraph confusing to say out loud). The array representation sidesteps all of that.

The Four Operations

Peek the Maximum: O(1)

The maximum is at index 0. One array access. You're done. Go home.

Insert: O(log n)

Append the new element to the end of the array (the rightmost open slot in the last level). Then restore the heap property by "sifting up": compare the new element with its parent, swap if the child is larger, repeat until the element is in place or reaches the root.

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

In the worst case you do one swap per level, and a complete binary tree with n nodes has height log(n). Insert is O(log n).

Extract Max: O(log n)

Removing the root sounds simple. It isn't. If you shift everything forward like a queue, that's O(n). Instead:

1. Swap the root with the last element.
2. Remove the last element (which is now the old root you wanted).
3. Sift the new root downward: compare with both children, swap with the larger child if that child is bigger, repeat until neither child beats you or you reach a leaf.

def extract_max(heap):
    if len(heap) == 1:
        return heap.pop()
    max_val = heap[0]
    heap[0] = heap.pop()
    i = 0
    n = len(heap)
    while True:
        left, right = 2 * i + 1, 2 * i + 2
        largest = i
        if left < n and heap[left] > heap[largest]:
            largest = left
        if right < n and heap[right] > heap[largest]:
            largest = right
        if largest == i:
            break
        heap[i], heap[largest] = heap[largest], heap[i]
        i = largest
    return max_val

One swap per level in the worst case. The trick of swapping with the last element before removing is what keeps it O(log n) instead of O(n). The heap shrinks from the bottom, not the middle.

Build a Heap from Scratch: O(n)

Here's one that surprises people. If you have n elements and want a valid heap, you could insert them one by one: that's O(n log n) total. Floyd's algorithm does it in O(n).

Start at the last non-leaf node (index n // 2 - 1) and sift each node down, working back toward the root:

def build_heap(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)

Build-heap is O(n), not O(n log n), because most nodes sit near the bottom and barely move.

Half the nodes are leaves doing zero work. A quarter are one level up and sift at most once. An eighth sift at most twice. Sum this geometric series and it converges to O(n). This gap between O(n) and O(n log n) is worth knowing cold because interviewers ask about it, and the answer genuinely surprises people who haven't seen the proof.

Max-Heap vs Min-Heap

The only difference is the comparison direction. A min-heap keeps the smallest element at the root. Every parent is less than or equal to its children. Everything else, including the array layout and all four operations, is identical.

Which one you need depends on whether you're pulling the maximum or the minimum from a changing set.

The Python Trap

Python's heapq module is a min-heap. There is no built-in max-heap. Python, in its infinite wisdom, decided that engineers would figure it out.

The standard workaround is negating your values:

import heapq

max_heap = []
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -30)

max_val = -heapq.heappop(max_heap)  # returns 30

This works cleanly for integers and floats. For objects, wrap them in a tuple with the negated priority as the first element, so comparison uses the priority rather than the object itself:

heapq.heappush(max_heap, (-priority, item))

The negation trick is so common that forgetting it in an interview is actively embarrassing. Add it to your mental checklist.

Java and C++

Java's PriorityQueue is also a min-heap by default. Pass a custom comparator to flip it:

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

C++ std::priority_queue is a max-heap by default. The opposite of most other languages. Keep that distinction straight when you switch between them, because confusing the two mid-interview is the kind of thing interviewers remember.

Why This Matters for Interviews

The heap shows up in disguise. The problem statement rarely says "use a heap." It describes a situation where you need the fastest access to the current extreme value of a changing set, and you have to recognize that yourself.

Top-K Largest Elements

"Find the K largest elements in an array of n numbers."

The first instinct is a max-heap: push everything in, pop K times. That works but costs O(n log n).

The faster approach uses a min-heap of size K. Scan the array and push each element. When the heap exceeds K elements, pop the minimum. At the end, the heap holds exactly the K largest elements.

Why a min-heap for a problem about largest elements? Because you want to evict the smallest candidate, not the largest. The min-heap's root is always the current weakest member of your K-best list. Every time something better comes along, the weakest drops out. This runs in O(n log K), which beats O(n log n) when K is much smaller than n.

For more on this pattern, see Top-K Elements: Every Heap Signal Worth Knowing.

Running Median

You have a stream of numbers and want the median after each insertion.

Use two heaps: a max-heap for the lower half and a min-heap for the upper half. Keep their sizes balanced within one element of each other. The median is the root of the larger heap, or the average of both roots when sizes are equal.

import heapq

lower = []   # max-heap (negate values)
upper = []   # min-heap

def add_num(num):
    heapq.heappush(lower, -num)
    if lower and upper and (-lower[0]) > upper[0]:
        heapq.heappush(upper, -heapq.heappop(lower))
    if len(lower) > len(upper) + 1:
        heapq.heappush(upper, -heapq.heappop(lower))
    elif len(upper) > len(lower):
        heapq.heappush(lower, -heapq.heappop(upper))

def find_median():
    if len(lower) > len(upper):
        return -lower[0]
    return (-lower[0] + upper[0]) / 2

The two-heap running median is one of those patterns where the setup looks overcomplicated until you've seen it three times and then it's obvious forever. It appears in LeetCode 295 and variants show up in onsite rounds at most major companies.

For a full list of problems that sharpen heap intuition, see Top 12 Heap Interview Problems: Every Pattern, One List.

Merge K Sorted Lists

Push the head node from each of the K lists into a min-heap keyed by value. Pop the minimum, add it to the result, push that node's .next. The heap holds the current frontier across all K lists. Each step costs O(log K), total O(n log K) for n elements across all lists.

Recognizing these patterns under time pressure is different from reading about them. SpaceComplexity runs voice-based mock interviews that put you in real conditions: explain your approach out loud, walk through the sift-down, defend your complexity analysis while someone watches the clock.

Complexity Reference

Operation	Time	Extra Space
Peek max	O(1)	O(1)
Insert	O(log n)	O(1)
Extract max	O(log n)	O(1)
Build heap	O(n)	O(1)
Heap sort	O(n log n)	O(1)

Heap sort achieves O(n log n) time with O(1) extra space, sorting in-place using the array itself. In practice it loses to quicksort on cache performance (pointer chasing through a non-sequential sift-down pattern is unfriendly to the prefetcher), but the space guarantee is real. See Heap Sort: Build-Heap Is O(n). Every Other Step Is O(n log n). for the full breakdown.

When a Heap Is the Wrong Choice

A heap is not a sorted structure. Finding an arbitrary element requires scanning the whole array: O(n). If you need ordered traversal or searching by value, use a balanced BST or a sorted array.

A heap also gives you no efficient way to access the second or third largest element without popping the first. If you need ranked access beyond the top, the heap is the wrong tool.

Use a heap when you repeatedly need the minimum or maximum from a changing set. Use a different structure for everything else. The heap is very good at one thing. Don't ask it to be a sorted array. It's doing its best.

For a direct comparison, see Heap vs Sorted Array: O(n) Insertion Is the Price of Full Order.

Key Takeaways

• A max-heap is a complete binary tree where every parent is greater than or equal to both children
• The root always holds the maximum; access is O(1)
• Insert and extract-max both run in O(log n) via sift-up and sift-down
• Build-heap runs in O(n) using Floyd's bottom-up algorithm, not O(n log n)
• Python's heapq is a min-heap; negate values to simulate a max-heap
• Key interview patterns: top-K elements, Kth largest, merge K sorted lists, running median

Further Reading

• Heap (data structure) on Wikipedia
• Python heapq documentation
• Java PriorityQueue documentation
• Binary Heap on GeeksforGeeks
• Build Heap complexity proof on Wikipedia