Data Structure1 Practice5 Interview

Heap

GuideCode Labs

Partially ordered tree-backed structure supporting efficient minimum or maximum extraction. This guide turns that contract into deliberate Python operations, interview invariants, and a runnable practice loop.

Recognize it when

Consider Heap when the prompt's constraints and required operations match this shape: Partially ordered tree-backed structure supporting efficient minimum or maximum extraction.

On this page · Mental Model

Checking your account…

Mental Model

A heap is a partially ordered binary tree stored in an array. In Python’s min-heap, every parent is no greater than its children, so the root at index zero is globally minimal. The rest of the array is not sorted; only the parent-child relation is guaranteed.

The Heap Order Invariant

For index i, children are 2*i + 1 and 2*i + 2. A push repairs one root-to-leaf path, and a pop moves the last item to the root before repairing one path downward. That gives O(log n) update and O(1) minimum lookup.

Build and Update a Min-Heap

heapq.heapify(values) transforms a list in O(n) time and mutates it. heappush and heappop are O(log n). heappushpop performs the combined operation efficiently and may immediately return a new item smaller than the existing root; heapreplace always removes the current root first and requires a nonempty heap.

Build and Consume a Min-Heap

Reference

import heapq

def consume_smallest(values, additions):
    heap = values.copy()
    heapq.heapify(heap)
    popped = []
    for value in additions:
        heapq.heappush(heap, value)
        popped.append(heapq.heappop(heap))
    return popped, sorted(heap)

Practice

Implement consume_smallest(values, additions). Heapify a copy, then push each addition and pop the current minimum; return popped values and sorted remaining values.

def consume_smallest(values, additions):
    heap = values.copy()
    popped = []
    for value in additions:
        heap.append(value)
        popped.append(heap.pop())
    return popped, sorted(heap)

Public tests

Verify minimum extraction after pushes

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

The heapq documentation(opens in a new tab) is explicit that the API is a min-heap. Max-priority code traditionally negates numeric priorities; state that representation instead of mentally reversing comparisons in scattered places.

Keep a Bounded Top K

To retain the k largest values, use a min-heap of at most k candidates. Its root is the weakest retained candidate. Once full, replace the root only when the new value is larger. The invariant is that the heap contains exactly the k largest values from the processed prefix.

Keep a Bounded Largest-K Heap

Reference

import heapq

def largest_k_sorted(values, k):
    heap = []
    for value in values:
        if len(heap) < k:
            heapq.heappush(heap, value)
        elif k and value > heap[0]:
            heapq.heapreplace(heap, value)
    return sorted(heap)

Practice

Implement largest_k_sorted(values, k). Keep at most k candidates in a min-heap and return retained values in ascending order.

def largest_k_sorted(values, k):
    return sorted(values)[:k]

Public tests

Verify bounded largest candidates

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose a Heap or Sort

Use a heap for repeated best-item extraction, streaming top k, or a changing frontier. Sort when all items are known and the complete order is required; sorting is often simpler and costs O(n log n). For one kth selection, quickselect may offer better average time but has a more delicate invariant.

Common Pitfalls

Reading the heap array as sorted gives wrong second/third-order results.
Pushing every item for top k wastes O(n) space instead of O(k).
Negated max-heap tuples need consistent signs in every comparison and returned value.
Equal tuple priorities compare later fields, which may be non-comparable objects.
Calling heapreplace on an empty heap raises an error.

Explain It in an Interview

Name the root meaning and the candidate invariant. Explain which single path an update repairs. Distinguish O(n) heapify from n separate O(log n) pushes, and state whether final sorting adds O(k log k). Avoid claiming the internal array is ordered beyond the heap property.

Update a Bounded Heap(opens in a new tab) practices candidate replacement. Kth Largest Element in an Array(opens in a new tab) tests whether heap size and root meaning are chosen for the requested rank.

Python Version Note

Python 3.11+

The examples use standard Python containers and syntax available in the supported browser runtime; Heap itself is taught as an interview abstraction.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Core Heap workflow	`O(n log k + k log k)`	`O(n log k + k log k)`	Streaming top-k selection needs only the current k best candidates, with the weakest candidate exposed at the heap root. After each value, the heap contains the largest min(k, processed_count) values seen so far.

Space

O(k) for the demonstrated Heap workflow.

Assumptions

Heap construction can be O(n); individual push and pop restore heap order in logarithmic time.
The bound counts the operations in Update a Bounded Heap and does not hide Python slicing, sorting, or copying.

Invariants Worth Saying Aloud

State the precise Heap invariant before coding and preserve it after every update, traversal step, or recursive return.
Streaming top-k selection needs only the current k best candidates, with the weakest candidate exposed at the heap root. This remains true after every accepted operation.
After each value, the heap contains the largest min(k, processed_count) values seen so far. This remains true after every accepted operation.

When To Use Or Avoid Heap

Use It When

Use Heap when its representation directly supports the prompt's repeated query or update.
Use it when the invariant can be stated before coding and preserved after every operation.

Choose Another Tool When

Avoid it when a simpler Python sequence or mapping communicates the same contract with less state.
Avoid it when building the structure costs more time or space than the number of required queries can justify.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Leaving the core transition unfinished

Placeholder code cannot preserve the Heap invariant or satisfy the public contract.

Prevent it: Implement the smallest complete transition and run the public tests before adding optimizations.

Avoid

def largest_k_sorted(values, k):
    pass

Use instead

import heapq

def largest_k_sorted(values, k):
    heap = []
    for value in values:
        if len(heap) < k:
            heapq.heappush(heap, value)
        elif k and value > heap[0]:
            heapq.heapreplace(heap, value)
    return sorted(heap)

Where you will hit this: Update a Bounded Heap(opens in a new tab)

Breaking the central invariant

Evicts whenever size reaches k instead of exceeds k, leaving at most k minus one retained values.

Prevent it: Keep this invariant visible while editing: State the precise Heap invariant before coding and preserve it after every update, traversal step, or recursive return.

Avoid

import heapq

def largest_k_sorted(values, k):
    heap = []
    for value in values:
        heapq.heappush(heap, value)
        if len(heap) >= k:
            heapq.heappop(heap)
    return sorted(heap)

Use instead

import heapq

def largest_k_sorted(values, k):
    heap = []
    for value in values:
        if len(heap) < k:
            heapq.heappush(heap, value)
        elif k and value > heap[0]:
            heapq.heapreplace(heap, value)
    return sorted(heap)

Where you will hit this: Update a Bounded Heap(opens in a new tab)

Hiding Python work inside the loop

Handle empty state, duplicate values, aliasing, and serialization boundaries explicitly in tests.

Prevent it: Account for every slice, copy, sort, membership test, and container mutation before claiming O(n log k + k log k).

Avoid

import heapq

def largest_k_sorted(values, k):
    heap = []
    for value in values:
        heapq.heappush(heap, value)
        if len(heap) >= k:
            heapq.heappop(heap)
    return sorted(heap)

Use instead

import heapq

def largest_k_sorted(values, k):
    heap = []
    for value in values:
        if len(heap) < k:
            heapq.heappush(heap, value)
        elif k and value > heap[0]:
            heapq.heapreplace(heap, value)
    return sorted(heap)

Where you will hit this: Kth Largest Element in an Array(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python heapq — Heap Queue Algorithm(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…

Heap Code Labs

Mental Model

The Heap Order Invariant

Build and Update a Min-Heap

Public tests

Keep a Bounded Top K

Public tests

Choose a Heap or Sort

Common Pitfalls

Explain It in an Interview

Python Version Note

Complexity & Invariants

Space

Assumptions

Invariants Worth Saying Aloud

When To Use Or Avoid Heap

Use It When

Choose Another Tool When

Common Pitfalls

Leaving the core transition unfinished

Breaking the central invariant

Hiding Python work inside the loop

Related Practice

Related Interview Problems

Reviewed References