Skip to content
Data Structures & Algorithms

Heaps and Maps interview questions and answers

44 questions, 24 with code. About 3 h 37 min to read them all.

By TestLab · Updated

Plan for an interview
44 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

What is a binary heap data structure?

A binary heap is a heap-ordered tree data structure that supports efficiently finding the minimum or maximum element. It is commonly implemented as a complete binary tree stored in an array, making it suitable for priority queues, scheduling algorithms, and other selection problems.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Properties

A binary heap has two important properties:

  • Heap-order property: Every parent is less than or equal to its children in a min-heap, or greater than or equal to them in a max-heap.

  • Complete-tree property: Every level is completely filled except possibly the last, which fills from left to right.

For a zero-based array representation:

  • Parent of index i: (i - 1) // 2

  • Left child of index i: 2 * i + 1

  • Right child of index i: 2 * i + 2

Because the tree is complete, the array has no gaps and avoids the memory overhead of explicit child pointers. Duplicate values are allowed, and the heap property does not imply that the remaining elements are globally sorted.

Operations and Complexity

The average-case figures below assume randomly ordered inputs.

Operation Best Average Worst Auxiliary space Reason
Peek at root O(1) O(1) O(1) O(1) The root is stored at index 0
Insert O(1) O(1) O(log n) O(1) iterative; O(log n) recursive The element moves upward only until the heap property is restored
Remove root O(1) O(log n) O(log n) O(1) iterative; O(log n) recursive The last element moves to the root and may sift downward
Build a heap O(n) O(n) O(n) O(1) iterative; O(log n) recursive Bottom-up heapification processes all nodes
Find an arbitrary value O(1) O(n) O(n) O(1) iterative; O(n) recursive Heap order does not preserve global ordering

The heap itself uses O(n) total space, including its stored elements. Auxiliary-space figures exclude the input heap but include the recursion stack for recursive implementations.

Building a heap in O(n), rather than O(n log n), is possible because the number of nodes at height h above the leaves decreases geometrically while each node can sift down at most O(h) levels. Thus, the total work is bounded by a series equivalent to O(n × Σ(h / 2^h)), which converges to O(n).

Min-Heap vs. Max-Heap

Heap type Root contains Typical use
Min-heap Smallest element Priority queues, Dijkstra’s algorithm with non-negative edge weights, event processing
Max-heap Largest element Scheduling, interval selection, streaming top-K calculations

Python’s heapq module operates on a list as a min-heap. A max-heap can be simulated by negating numeric values or by storing (-priority, item) tuples. When priorities can tie and the item payloads should not determine the ordering, use a unique counter such as (-priority, counter, item).

Small Example

Consider the min-heap array [1, 5, 3, 8, 6]. Its root is 1; its children are 5 and 3; and 5 has children 8 and 6.

  1. Insert 2, which is appended at index 5.

  2. Its parent is at index (5 - 1) // 2 = 2, containing 3.

  3. Because 2 < 3, swap them, producing [1, 5, 2, 8, 6, 3].

  4. Compare 2 with its new parent at index 0, containing 1.

  5. Since 2 >= 1, stop. The resulting array satisfies the min-heap property.

Common Pitfalls

  • Confusing heap order with sorted order: Only the root is guaranteed to be the minimum or maximum.

  • Assuming heapq is a max-heap: Negate values or use negative priorities for max-heap behavior.

  • Using a nonexistent emptiness API: heapq.isempty() is not available; use if not heap or len(heap) == 0. Accessing or removing the root of an empty heap raises IndexError.

  • Ignoring ties: Add a counter before the item payload when equal priorities must not cause payload comparison or alter FIFO ordering.

  • Indexing errors: The root is index 0, and the child formulas are 2 * i + 1 and 2 * i + 2.

  • Unexpected mutation: heapq.heapify rearranges its list in place; copy the list first if the original ordering must be preserved.

  • Edge cases: Empty heaps, one-element heaps, duplicates, and negative values should be handled explicitly where applicable.

  • Common follow-ups: Implement sift-up and sift-down, justify why heapify is O(n), and explain when to choose a heap instead of a sorted list.

2

What is a priority queue in data structures?

A priority queue is an abstract data structure that removes elements according to their priority rather than their insertion order. A binary heap is the most common implementation, although sorted lists, balanced trees, and other structures can also provide priority-queue behavior.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

A priority queue normally supports these operations:

  • Insert: add an element with a given priority.

  • Remove minimum: remove the element with the highest priority.

  • Peek: inspect that element without removing it.

  • Size or empty check: determine whether the queue contains any elements.

The terminology varies. This answer uses the common min-priority queue convention: a smaller key means higher priority. If larger keys should be removed first, the implementation can use negated numeric keys or reverse the comparison logic.

Unlike a FIFO queue, a priority queue is not normally first-in, first-out. Elements with equal priorities require an explicit tie-breaking policy, such as insertion order.

Binary Heap Implementation

A binary heap is a complete binary tree stored in an array. For an element at index i:

  • Its left child is at 2 * i + 1.

  • Its right child is at 2 * i + 2.

  • Its parent is at (i - 1) // 2.

The heap maintains the heap property: every parent is at least as high in priority as its children. Consequently, the root contains the next element to remove.

Insertion places the new element at the end of the array and moves it upward until the heap property is restored. Removal replaces the root with the last element and moves it downward until the heap property is restored again.

Python’s heapq module provides a production-ready min-heap. For a max-heap, negate numeric priorities. For equal priorities, use a tuple such as (-priority, counter, value) so that Python does not attempt to compare the values themselves.

Complexity

For a binary heap containing n elements:

Operation Best Average Worst
Peek O(1) O(1) O(1)
Insert O(1) O(log n) O(log n)
Remove minimum O(1) O(log n) O(log n)
Build a heap O(n) O(n) O(n)

The heap height is O(log n), so an insertion or removal may sift through O(log n) levels.

Building a heap in O(n) is possible because bottom-up heapification does not sift every element through the full height. Most elements are near the leaves and move only a short distance; summing the work across all tree levels gives O(n), rather than O(n log n).

The queue requires O(n) space for its stored elements. Auxiliary space beyond those elements is O(1), and this implementation uses no recursion stack. If the original input collection is retained in addition to the heap, it requires another O(n) space.

With a dynamically growing array such as Python’s list, insertion remains O(log n) amortized, although an individual insertion that triggers array resizing can temporarily cost O(n).

Example Walkthrough

Consider a queue where smaller task numbers have higher priority:

Operation Heap keys after operation Removed element
Insert (8, "email") [8] —
Insert (3, "deploy") [3, 8] —
Insert (5, "backup") [3, 8, 5] —
Remove minimum [5, 8] 3
Insert (1, "incident") [1, 8, 5] —
Remove minimum [5, 8] 1

The array may not be globally sorted, but its first element is always the correct next removal.

Common Pitfalls

  • Empty queue: peek and removal should fail explicitly rather than return an invalid element.

  • Single element: insertion and removal work without special cases.

  • Duplicate priorities: define whether earlier or later insertions win.

  • Negative priorities: they are valid when smaller values mean higher priority.

  • Already sorted input: it is valid, though rebuilding the heap can still take O(n).

  • Maps are not heaps: a dict can store priorities but does not efficiently find the minimum key.

  • Integer overflow: in fixed-width languages, calculate priorities using a sufficiently wide integer type.

  • Tie-breakers: when storing tuples in heapq, include a monotonically increasing counter if equal-priority values are otherwise incomparable.

3

How do max-heap and min-heap ordering properties compare?

A binary heap is a complete binary tree in which every parent satisfies an ordering relation with its children. In a max-heap, each parent is greater than or equal to its children, so the largest element is at the root; in a min-heap, each parent is less than or equal to its children, so the smallest element is at the root.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Heap Property Comparison

Property Max-heap Min-heap
Parent-child rule parent >= children parent <= children
Root contains Largest element Smallest element
Useful for Processing the highest-priority item first Processing the lowest-priority item first
Typical applications Priority queues, task scheduling by highest priority Dijkstra’s algorithm, event processing, task scheduling by lowest priority

The comparisons are non-strict, so duplicate values are allowed. Both structures are usually not fully sorted: only the relationship between a parent and its direct children is guaranteed, and the heap property then holds transitively for all descendants.

Structural Invariants

A binary heap is stored efficiently as an array. For an element at zero-based index i:

  • Left child: 2 * i + 1

  • Right child: 2 * i + 2

  • Parent: (i - 1) // 2

Because the tree is complete, the array has no gaps. This compact layout gives an array representation with O(n) total storage and avoids the pointer overhead of a node-based tree.

Small Example

Consider the max-heap array [9, 7, 8, 3, 2, 6, 1]. Its relationships are:

  1. The root 9 has children 7 and 8, and 9 >= 7 and 9 >= 8.

  2. The node 7 has children 3 and 2, and 7 >= 3 and 7 >= 2.

  3. The node 8 has children 6 and 1, and 8 >= 6 and 8 >= 1.

  4. The remaining values are leaves and therefore need no child comparisons.

A corresponding min-heap is [1, 2, 3, 9, 7, 6, 8]. Its root is 1; the other parent-child relationships are 2 <= 9, 2 <= 7, and 3 <= 8.

Operation Complexity

For a heap containing n elements:

Operation Best case Average case Worst case Auxiliary space
Peek at root O(1) O(1) O(1) O(1)
Insert O(1) O(log n) O(log n) O(1)
Remove root O(log n) O(log n) O(log n) O(1)
Build a heap O(n) O(n) O(n) O(1)

Insertion and removal adjust the heap along one root-to-leaf path, whose length is at most O(log n). Building a heap bottom-up takes O(n), not O(n log n), because most nodes are near the leaves and have small subtrees; the combined cost of all sift-down operations forms a convergent geometric series.

Total space is O(n) when the stored heap array, or input array, is counted. Additional auxiliary space is O(1) because these operations are iterative, modify the array in place, and use no recursion stack.

Common Pitfalls and Interview Tips

  • Confusing heap order with sorted order: only the root is guaranteed to be the maximum or minimum.

  • Using strict comparisons: use >= or <= so equal values remain valid.

  • Ignoring completeness: heap order alone does not make a binary tree a binary heap.

  • Edge cases: an empty heap has no root, while a one-element heap is both its minimum and maximum. Negative values and duplicates are valid.

  • Sorted input: an ascending array is already a valid min-heap, and a descending array is already a valid max-heap.

  • Python library convention: Python 3.12’s heapq implements a min-heap. For a max-heap, store negated numeric values or use (-priority, counter, item) tuples, where an increasing counter prevents comparison of non-comparable items when priorities tie.

  • heapq.nlargest returns the largest elements in descending order, while heapq.nsmallest returns the smallest elements in ascending order.

  • A common follow-up asks how heapq.heapify achieves O(n) time or how two heaps can maintain a running median in O(log n) per insertion.

4

How is heap property maintained after insertion and deletion?

Heap property is maintained by sift-up after insertion and sift-down after removing the root. These operations restore the parent-child ordering invariant while preserving the heap’s complete-tree shape.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A binary heap is a complete binary tree stored in an array. For a zero-based index i, its parent is at (i - 1) // 2, and its children are at 2 * i + 1 and 2 * i + 2.

  • Insertion — sift up:

  • Append the new value to the next available position in the level-order array. This preserves completeness, although the position is not necessarily the bottom-rightmost position.

  • Compare the new element with its parent.

  • In a min-heap, swap them if the child is smaller than the parent.

  • Continue moving upward until the parent is less than or equal to the child, or the element reaches the root.

  • Root deletion — sift down:

  • Save and remove the root.

  • Move the last array element to the root, preserving the complete-tree shape.

  • Compare it with its children and swap it with the smaller child if it violates the min-heap property.

  • Continue until the element is less than or equal to both children or it is a leaf.

For a max-heap, the comparisons are reversed. Python’s heapq is a min-heap; a max-heap can be simulated by storing negated values.

Complexity Analysis

Operation Best Average Worst Auxiliary Space
Peek O(1) O(1) O(1) O(1)
Insert O(1) O(log n) amortized O(log n) for heap repair; O(n) for this list-backed method if append reallocates O(1)
Delete root O(1) O(log n) O(log n) O(1)
Heapify O(n) O(n) O(n) O(1)

The heap repair itself is O(log n) worst-case because an element traverses at most the tree height. In this Python implementation, list.append is amortized O(1), but an occasional reallocation can make one insertion O(n).

Heapify is O(n), not O(n log n), because sift-down work depends on subtree height. Summing those heights gives a geometric series: O(n/2) + O(n/4 * 2) + O(n/8 * 3) + ... = O(n).

Space is O(1) auxiliary because the implementation is iterative and uses no recursion stack. This excludes the heap’s own O(n) element storage.

Code Example

class MinHeap:
    """A binary min-heap implemented using a list."""

    def __init__(self) -> None:
        self.heap: list[int] = []

    def insert(self, value: int) -> None:
        """Append a value and restore the heap property by sifting up."""
        self.heap.append(value)
        self._sift_up(len(self.heap) - 1)

    def delete(self) -> int:
        """Remove and return the root, restoring the heap property."""
        if not self.heap:
            raise IndexError("delete from an empty heap")

        root = self.heap[0]
        last = self.heap.pop()
        if self.heap:
            self.heap[0] = last
            self._sift_down(0)
        return root

    def _sift_up(self, index: int) -> None:
        """Move an element upward until its parent is less than or equal."""
        while index > 0:
            parent = (index - 1) // 2
            if self.heap[index] < self.heap[parent]:
                self.heap[index], self.heap[parent] = (
                    self.heap[parent],
                    self.heap[index],
                )
                index = parent
            else:
                break

    def _sift_down(self, index: int) -> None:
        """Move an element downward until both children are greater or equal."""
        size = len(self.heap)
        while 2 * index + 1 < size:
            left = 2 * index + 1
            right = 2 * index + 2
            smallest = left

            if right < size and self.heap[right] < self.heap[left]:
                smallest = right

            if self.heap[smallest] < self.heap[index]:
                self.heap[smallest], self.heap[index] = (
                    self.heap[index],
                    self.heap[smallest],
                )
                index = smallest
            else:
                break


heap = MinHeap()
heap.insert(10)
heap.insert(5)
heap.delete()  # Returns 5; heap.heap is now [10].

Common Pitfalls

  • Off-by-one errors: Use (i - 1) // 2 for the parent and check that the left child exists before accessing either child.

  • Integer overflow: In fixed-width languages, calculating child indices can overflow for very large arrays; use sufficiently wide integer types or safe arithmetic.

  • Empty and single-element heaps: Deletion from an empty heap must raise an error, and deleting the only element must not trigger sift-down.

  • Duplicates and negative values: Both are supported because the property compares keys using <=; equal values need not be swapped.

  • Already ordered input: Inserting nondecreasing values into a min-heap causes no sift-up movement, although list resizing can still affect one insertion’s cost.

  • Mutation: Sift operations intentionally mutate the backing array, so do not use an externally shared list without accounting for those changes.

  • Typical follow-up: Explain how to build a heap in O(n) time, inspect the minimum in O(1), and implement a max-heap.

5

How do you insert an item into a min-heap?

Heap insertion appends the new item to the heap’s array and then restores the min-heap property by moving it upward, or sifting up, whenever it is smaller than its parent. The heap remains a complete binary tree because every insertion goes into the next available array position.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A binary min-heap is stored in an array, with the heap-order property that every parent is less than or equal to its children.

For an element at index i:

  • Left child: 2 * i + 1

  • Right child: 2 * i + 2

  • Parent: (i - 1) // 2

Insertion proceeds as follows:

  1. Append the new item at the end of the array.

  2. Compare it with its parent.

  3. If the child is smaller, swap them and continue moving upward.

  4. Stop when the item reaches the root or its parent is less than or equal to it.

The swap-and-continue operation is called sift-up. Equal elements do not need to be swapped because a min-heap permits a parent and child to have the same value.

Example Walkthrough

Starting with the valid min-heap [3, 7, 5], insert 2:

Step Heap state Action
1 [3, 7, 5, 2] Append 2 at index 3
2 [3, 2, 5, 7] 2 is smaller than parent 7, so swap
3 [2, 3, 5, 7] 2 is smaller than parent 3, so swap
4 [2, 3, 5, 7] 2 reaches the root

The final array satisfies both the complete-tree structure and the min-heap property.

Complexity

For a heap containing n items before insertion:

Case Time Reason
Best O(1) The item is appended and no upward movement is needed
Average O(log n) The item may sift upward along the heap’s height
Worst O(log n) The item can move from the last position to the root

A complete binary tree has height O(log n), so a sift-up performs at most O(log n) comparisons and swaps.

Auxiliary space: O(1), because insertion is iterative and uses no recursion stack. The existing heap occupies O(n) total storage and is not copied. If the entire stored heap is counted, total space is O(n).

For comparison, a heap’s peek operation is O(1), pop is O(log n), and heapify is O(n). heapify is O(n) because most nodes are near the leaves and have little upward work; the total work across all levels sums to O(n), rather than O(n log n).

Code Example

def insert_min_heap(heap: list[int], item: int) -> None:
    """Insert an item into a min-heap in place using sift-up."""
    heap.append(item)
    child_index = len(heap) - 1

    while child_index > 0:
        parent_index = (child_index - 1) // 2

        # The min-heap property is already restored.
        if heap[parent_index] <= heap[child_index]:
            break

        heap[parent_index], heap[child_index] = (
            heap[child_index],
            heap[parent_index],
        )
        child_index = parent_index


heap = [3, 7, 5]
insert_min_heap(heap, 2)
print(heap)  # [2, 3, 5, 7]

Python’s heapq.heappush performs the equivalent insertion for production code. The implementation above shows the internal operation directly.

Common Pitfalls

  • Using the wrong parent formula: The parent of index i is (i - 1) // 2, not i // 2.

  • Comparing with the wrong child: During insertion, the new item moves upward; it is not compared with its children.

  • Forgetting the empty-heap case: After appending to an empty heap, the item is already at the root, so the loop must not run.

  • Mutating unexpectedly: This implementation changes the supplied list in place. Copy it first if the caller requires the original list to remain unchanged.

  • Assuming the array is fully sorted: A heap is only partially ordered; sibling subtrees need not be sorted relative to each other.

  • Edge cases: One element, duplicates, and negative values work naturally. Disconnected graphs and cycles are graph-specific concerns and do not apply to heap insertion.

  • Common follow-up: Interviewers may ask how to implement deletion of the root, which requires replacing it with the last item and then applying sift-down.

6

How do heap-based and array-based priority queues differ?

A priority queue removes elements according to priority rather than insertion order. Heap-based implementations provide efficient O(log n) insertion and removal, while array-based implementations are simpler but trade those operations for cheaper insertion, removal, or simpler memory layout.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Difference

A binary heap is logically a complete binary tree stored in an array, with the children of index i at 2i + 1 and 2i + 2. Its heap invariant keeps the highest-priority element at the root, allowing fast access to the next item.

An array-based priority queue can be:

  • Unsorted array: append new elements and scan for the highest priority when removing.

  • Sorted array: keep priorities ordered and place the minimum at a known endpoint.

Although a heap is physically array-backed, its order is maintained specifically to preserve the heap invariant.

Complexity Comparison

The table uses a min-priority queue; max-priority queues have symmetric behavior.

Implementation Operation Best Average Worst Reason
Unsorted array Insert O(1) O(1) amortized O(n) Append is amortized constant-time, but resizing can cost O(n)
Unsorted array Remove minimum O(n) O(n) O(n) Every remaining element may need inspection
Unsorted array Peek minimum O(n) O(n) O(n) A scan is needed unless the minimum is cached
Sorted array, minimum at end Insert O(1) O(n) O(n) A new minimum can be appended; otherwise elements shift
Sorted array, minimum at end Remove minimum O(1) O(1) O(1) The minimum is removed from the end
Sorted array, minimum at end Peek minimum O(1) O(1) O(1) The minimum is at a known endpoint
Binary heap Insert O(1) O(log n) O(log n) Sift-up traverses at most the heap height
Binary heap Remove minimum O(log n) O(log n) O(log n) Replace the root and sift down
Binary heap Peek minimum O(1) O(1) O(1) The minimum is stored at the root
Binary heap Build from a collection O(n) O(n) O(n) Bottom-up heapification performs decreasing work by level

If the minimum is kept at the front of a packed sorted array, removing it shifts the remaining elements and costs O(n). In either orientation, binary search finds a known priority in O(log n), but insertion and removal can still require shifting.

Heap construction is O(n), not O(n log n), because most nodes are near the leaves and sift only a small number of levels. The total work is proportional to Σ(n / 2^(h+1) × h), which converges to O(n).

Memory and Implementation Trade-offs

  • Plain heap: Uses O(n) total storage and O(1) auxiliary space, excluding stored elements. An iterative implementation has O(1) recursion stack space.

  • Indexed heap: An item-to-index map permits arbitrary removal and priority changes, but adds O(n) auxiliary storage. The heap update is O(log n) after the lookup; the lookup is O(1) average and O(n) worst case for a hash map.

  • Unsorted array: Uses O(n) total storage and O(1) auxiliary space, with the simplest implementation and fastest insertion.

  • Sorted array: Uses O(n) total storage and O(1) auxiliary space for its operations. Its total space is O(n) including the stored queue elements.

  • Stability: A sorted array can preserve insertion order among equal priorities by inserting after existing equals. A heap requires a monotonically increasing insertion sequence number or an equivalent stable tie-breaker; an arbitrary deterministic tie-breaker alone is not stable.

Practical Behavior

For a job scheduler, an unsorted array suits insertion-heavy workloads with rare removals. A sorted array is useful when ordered or stable processing matters. A binary heap is the usual choice for repeated insertion and extraction, such as event simulation and Dijkstra’s algorithm with non-negative edge weights.

Important edge cases behave consistently:

  • Empty queue: Removal and peeking have no element to return; insertion remains valid.

  • One element: Removing it takes O(1) and requires no shifting.

  • Duplicates: Every occurrence is retained; equal-priority order may be arbitrary unless stability is implemented.

  • Negative priorities: They are valid; the comparison determines priority.

  • Already sorted input: It favors direct endpoint insertion in a sorted array, but does not change heap insertion or extraction bounds.

Choosing an Approach

  • Choose an unsorted array for simple batch processing, rare removals, or insertion-heavy workloads.

  • Choose a sorted array when stable ordering, ordered access, or O(1) endpoint removal matters more than insertion speed.

  • Choose a binary heap for predictable O(log n) insertion and extraction.

  • Python’s standard library has no ordered tree map. bisect supports O(log n) lookup in a sorted list, but insertion remains O(n); third-party sorted containers are not part of the standard library.

Common Pitfalls

  • Do not describe heap peeking as O(log n) or heap removal as O(n).

  • Do not claim sorted-array insertion is O(log n) merely because binary search locates the insertion point.

  • Do not confuse amortized O(1) array append with worst-case O(1); resizing can make one append O(n).

  • Do not equate a deterministic heap tie-breaker with stability.

  • Interviewers commonly ask about empty queues, duplicates, negative priorities, decreasing priorities, and arbitrary deletion.

7

How do you implement a binary heap with a dynamic array?

A binary heap can be implemented efficiently by storing its complete binary tree in a dynamic array. Array indices determine parent-child relationships, allowing insertion, deletion, and restoration of the heap property without explicit tree nodes.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For an array-backed binary heap with zero-based indexing:

  • The root is at index 0.

  • The left child of index i is at 2 * i + 1.

  • The right child of index i is at 2 * i + 2.

  • The parent of index i is at (i - 1) // 2.

The implementation below maintains a min-heap, meaning the smallest element is always at the root.

  • Push: Append the value and sift it upward while it is smaller than its parent.

  • Pop: Remove the root, move the last array element to the root, and sift it downward.

  • Peek: Return the root without modifying the heap.

  • Heapify: Build the heap from bottom to top, sifting every internal node downward.

Python’s list acts as a dynamic array: it grows automatically and amortizes the cost of appending across many operations.

Complexity

Operation Best Average Worst Reason
push O(1) O(log n) amortized O(n) Sifting takes O(log n); an occasional list resize copies O(n) elements
pop O(1) O(log n) O(log n) The replacement may sift through the full heap height
peek O(1) O(1) O(1) The root is accessed directly
Heap construction O(n) O(n) O(n) Bottom-up sift-down work sums to O(n) across levels
Space O(n) O(n) O(n) The backing array stores all elements

Heap construction is O(n), not O(n log n), because leaves do no sift work, and the number of nodes at each successive level above them halves. Summing the possible sift-down work by level gives approximately n/2 × 0 + n/4 × 1 + n/8 × 2 + ... = O(n).

Counting the stored heap elements, space is O(n). Auxiliary space beyond the heap is O(1), including the recursion stack, because all operations are iterative. The original input collection is not counted separately.

Code Example

from collections.abc import Iterable
from typing import Generic, Protocol, TypeVar


class Comparable(Protocol):
    def __lt__(self, other: object, /) -> bool: ...


T = TypeVar("T", bound=Comparable)


class BinaryHeap(Generic[T]):
    """Array-backed min-heap with amortized O(log n) push and O(log n) pop."""

    def __init__(self, values: Iterable[T] = ()) -> None:
        self._items: list[T] = list(values)
        self._heapify()

    def __len__(self) -> int:
        return len(self._items)

    def peek(self) -> T:
        """Return the smallest element without removing it."""
        if not self._items:
            raise IndexError("peek from an empty heap")

        return self._items[0]

    def push(self, value: T) -> None:
        """Insert a value and restore the min-heap property."""
        self._items.append(value)
        self._sift_up(len(self._items) - 1)

    def pop(self) -> T:
        """Remove and return the smallest element."""
        if not self._items:
            raise IndexError("pop from an empty heap")

        minimum = self._items[0]
        last_value = self._items.pop()

        if self._items:
            self._items[0] = last_value
            self._sift_down(0)

        return minimum

    def _heapify(self) -> None:
        for index in range(len(self._items) // 2 - 1, -1, -1):
            self._sift_down(index)

    def _sift_up(self, index: int) -> None:
        while index > 0:
            parent = (index - 1) // 2

            if not (self._items[index] < self._items[parent]):
                break

            self._items[index], self._items[parent] = (
                self._items[parent],
                self._items[index],
            )
            index = parent

    def _sift_down(self, index: int) -> None:
        size = len(self._items)

        while True:
            left = 2 * index + 1
            if left >= size:
                break

            smaller_child = left
            right = left + 1

            if right < size and self._items[right] < self._items[left]:
                smaller_child = right

            if not (self._items[smaller_child] < self._items[index]):
                break

            self._items[index], self._items[smaller_child] = (
                self._items[smaller_child],
                self._items[index],
            )
            index = smaller_child


heap = BinaryHeap([1, 3, 2, 7, 5])
heap.push(4)

print(heap.peek())  # 1
print(heap.pop())   # 1

Example Walkthrough

Starting with the valid min-heap [1, 3, 2, 7, 5]:

  1. Pushing 4 appends it: [1, 3, 2, 7, 5, 4].

  2. Its parent is at index 2 and contains 2.

  3. Because 4 is not smaller than 2, no swap occurs and the sift-up stops.

  4. The root remains 1, so both peek() and pop() return 1.

Common Pitfalls

  • Incorrect child indices: Use 2 * i + 1 and 2 * i + 2 for zero-based arrays.

  • Empty heaps: peek and pop raise IndexError; the constructor accepts an empty iterable.

  • Other inputs: One element, duplicate values, negative numbers, and already sorted input are all handled. Heap elements must be mutually comparable.

  • Max heaps: Negate numeric values, or store (-priority, counter, item) with a unique increasing counter so equal priorities do not cause payload comparisons.

  • Assuming heapify is O(n log n): Bottom-up construction is O(n) because most sift operations process only a small subtree.

  • Counting recursion space: This implementation is iterative, so no call-stack space is required.

  • Mutating the source input: The constructor copies the iterable before heapifying, leaving the caller’s original collection unchanged.

8

What are common ways to implement a priority queue?

A priority queue removes elements according to priority rather than insertion order. Common implementations include binary heaps, sorted arrays, balanced search trees, and unsorted arrays, with binary heaps providing the best general-purpose performance.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Implementation Choices

Implementation Push Pop Minimum Peek Total Space Best Use
Binary heap O(log n) O(log n) O(1) O(n) General-purpose priority queues
Sorted array, minimum at end O(n) O(1) O(1) O(n) Small queues or frequent minimum access
Balanced search tree O(log n) O(log n) O(log n), or O(1) with cached minimum O(n) When ordered traversal is also required
Unsorted array O(1) amortized O(n) O(n) O(n) Frequent insertions with rare removals

Except for dynamic-array append, the listed deterministic operations have the same best, average, and worst cases. Unsorted-array insertion is O(1) amortized, but one append can cost O(n) when the backing list grows; preallocated storage gives O(1) worst-case insertion.

  • Binary heap: The standard choice because push and pop require only O(log n) heap-adjustment time.

  • Sorted array: Store priorities in descending order so the minimum is at the end. A binary search (for example bisect.insort(items, p, key=lambda x: -x) on Python 3.10+) finds an insertion position in O(log n), but shifting elements still makes insertion O(n). An ascending layout instead has O(n) front removal.

  • Balanced search tree: Python has no built-in tree map. Use a third-party balanced-tree map for this row. The third-party sortedcontainers.SortedList offers sorted order, but it is list-backed, so front insertion or removal can cost O(n) because elements shift.

  • Unsorted array: Simple to implement, but finding the minimum requires scanning all elements.

The total-space figures count the priority queue’s own storage and exclude the original input. Auxiliary space per operation is O(1) for heaps and arrays. Recursive balanced-tree operations use an additional O(log n) stack, while iterative implementations can use O(1). Constructing a heap by copying an input collection requires O(n) space in addition to the original input.

Binary Heap Mechanics

A binary heap is a complete binary tree stored in an array. For zero-based index i:

  • Left child: 2 * i + 1

  • Right child: 2 * i + 2

  • Parent of a non-root node: (i - 1) // 2

In a min-heap, every parent is no greater than its children, so the minimum is always at index 0.

  • Push: Append the item and sift it upward, taking O(log n).

  • Pop: Replace the root with the final item and sift it downward, taking O(log n).

  • Peek: Read index 0, taking O(1).

  • Heapify: Process internal nodes bottom-up in O(n). At depth h, there are O(n / 2^h) nodes with sift cost O(h), and the sum of h / 2^h is O(n).

Python’s heapq is a standard-library min-heap. A max-heap can use negated numeric priorities. If storing tuples, use (-priority, sequence_number, item) so equal priorities do not cause item values to be compared.

Worked Example

Starting with the valid min-heap [1, 2, 3, 4, 5]:

  1. Push 0: [1, 2, 3, 4, 5, 0]

  2. Compare 0 with parent 3 and swap: [1, 2, 0, 4, 5, 3]

  3. Compare 0 with parent 1 and swap: [0, 2, 1, 4, 5, 3]

  4. Pop returns 0, moves 3 to the root, and sifts it down to [1, 2, 3, 4, 5].

Code Example

from collections.abc import Iterable
from typing import Generic, TypeVar

T = TypeVar("T")


class BinaryMinHeap(Generic[T]):
    """Implement the core operations of a min-oriented binary heap."""

    def __init__(self, items: Iterable[T] | None = None) -> None:
        self._items: list[T] = list(items) if items is not None else []

        # Bottom-up heap construction: O(n).
        for index in range(len(self._items) // 2 - 1, -1, -1):
            self._sift_down(index)

    def __len__(self) -> int:
        return len(self._items)

    def peek(self) -> T:
        if not self._items:
            raise IndexError("peek from empty heap")
        return self._items[0]

    def push(self, item: T) -> None:
        self._items.append(item)
        self._sift_up(len(self._items) - 1)

    def pop(self) -> T:
        if not self._items:
            raise IndexError("pop from empty heap")

        minimum = self._items[0]
        last_item = self._items.pop()

        if self._items:
            self._items[0] = last_item
            self._sift_down(0)

        return minimum

    def _sift_up(self, index: int) -> None:
        while index > 0:
            parent = (index - 1) // 2
            if self._items[parent] <= self._items[index]:
                break

            self._items[parent], self._items[index] = (
                self._items[index],
                self._items[parent],
            )
            index = parent

    def _sift_down(self, index: int) -> None:
        while True:
            left = 2 * index + 1
            right = 2 * index + 2
            smallest = left

            if right < len(self._items) and self._items[right] < self._items[left]:
                smallest = right

            if smallest >= len(self._items):
                break

            if self._items[index] <= self._items[smallest]:
                break

            self._items[index], self._items[smallest] = (
                self._items[smallest],
                self._items[index],
            )
            index = smallest


heap = BinaryMinHeap([1, 2, 3, 4, 5])
heap.push(0)
print(heap.pop())  # 0

Common Pitfalls

  • Empty and single-element heaps: pop and peek must check emptiness explicitly; removing the only element requires no sift-down.

  • Duplicates, negative priorities, and ties: Numeric duplicates and negatives are supported, but equal-priority removal order is unspecified. Use (priority, sequence_number, item) for FIFO ties.

  • Already sorted input: An ascending list already satisfies the min-heap property; descending input is accepted and rearranged by heapification.

  • Mutation and off-by-one errors: heapq.heapify mutates its input, while the example copies the input. Child and parent indices must use zero-based formulas.

  • Overflow in other languages: Large priority arithmetic can overflow, particularly when priorities are negated.

  • Graph traversal: For unweighted BFS-style traversal, mark vertices visited when enqueued to handle cycles; disconnected components require separate starts. For Dijkstra, maintain a distance map, allow improved vertices to be enqueued again, skip stale entries, and require non-negative weights.

  • Interview follow-ups: Common questions cover stable ties, decrease-key operations, thread safety, and why heap construction is O(n) rather than O(n log n).

9

How does lazy deletion work in a heap?

Lazy deletion invalidates a queued heap item without immediately removing it from the heap’s underlying array. Instead, the item is marked as deleted, and the deletion is completed only when the stale entry reaches the root during pop or peek.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A heap efficiently removes its minimum or maximum element from the root, but finding and removing an arbitrary element can require an O(n) search. Lazy deletion avoids that search:

  1. Assign every inserted entry a unique token.

  2. Store the entry and its token in the heap.

  3. To delete an entry, mark its token in a deleted set.

  4. When removing entries from the heap’s root, discard any whose token is marked.

  5. Continue until a live entry is found or the heap becomes empty.

The token distinguishes separate heap entries even when they contain identical items or priorities.

Purpose and Trade-offs

  • Fast invalidation: Marking a token is O(1) on average.

  • Simple implementation: The heap does not need indexes for every entry.

  • Deferred cleanup: A deleted entry continues consuming memory until it reaches the root.

  • Use case: Task schedulers, graph algorithms, and caches often invalidate queued work when conditions change.

An indexed heap can physically delete an arbitrary entry in O(log n), but it must maintain an index for every element. Lazy deletion trades that bookkeeping for deferred cleanup.

Complexity

Operation Best case Average case Worst case Reason
push O(1) O(log n) amortized O(log n) for heap work The entry moves toward the root through at most the tree height; backing-list growth is amortized
Mark deleted O(1) O(1) O(n) Token lookup uses hashing; collisions can make set lookup linear
pop, no stale root O(log n) O(log n) O(log n) The root is replaced and sifted down
pop, k stale entries skipped O(log n) Depends on stale-entry rate O((k + 1) log n) Each stale root removal may sift through O(log n) levels

Across the lifetime of n inserted entries, cleanup costs at most O(n log n), giving an amortized O(log n) cost per entry. Space usage is O(n) total, including O(d) deletion metadata for d stale entries; the original input is not counted, and the recursion stack is O(1) because the implementation is iterative.

Code Example

from typing import Generic, TypeVar

T = TypeVar("T")


class LazyMinHeap(Generic[T]):
    """A min-heap that supports marking entries as deleted."""

    def __init__(self) -> None:
        self._heap: list[tuple[int, int, T]] = []
        self._tokens: set[int] = set()
        self._deleted: set[int] = set()
        self._next_token = 0

    def push(self, priority: int, item: T) -> int:
        token = self._next_token
        self._next_token += 1

        self._heap.append((priority, token, item))
        self._tokens.add(token)
        self._sift_up(len(self._heap) - 1)
        return token

    def delete(self, token: int) -> bool:
        if token not in self._tokens or token in self._deleted:
            return False

        self._deleted.add(token)
        return True

    def pop(self) -> tuple[int, T]:
        if not self._heap:
            raise IndexError("pop from empty heap")

        while self._heap:
            priority, token, item = self._heap[0]
            was_deleted = token in self._deleted
            self._remove_root()

            if not was_deleted:
                return priority, item

        raise IndexError("pop from empty heap")

    def _remove_root(self) -> None:
        token = self._heap[0][1]
        last = self._heap.pop()
        if self._heap:
            self._heap[0] = last
            self._sift_down(0)

        self._tokens.discard(token)
        self._deleted.discard(token)

    def _sift_up(self, index: int) -> None:
        while index > 0:
            parent = (index - 1) // 2
            if self._key(self._heap[index]) >= self._key(self._heap[parent]):
                break

            self._heap[index], self._heap[parent] = (
                self._heap[parent],
                self._heap[index],
            )
            index = parent

    def _sift_down(self, index: int) -> None:
        while True:
            left = 2 * index + 1
            right = left + 1
            if left >= len(self._heap):
                break

            smaller = left
            if (
                right < len(self._heap)
                and self._key(self._heap[right]) < self._key(self._heap[left])
            ):
                smaller = right

            if self._key(self._heap[index]) <= self._key(self._heap[smaller]):
                break

            self._heap[index], self._heap[smaller] = (
                self._heap[smaller],
                self._heap[index],
            )
            index = smaller

    @staticmethod
    def _key(entry: tuple[int, int, T]) -> tuple[int, int]:
        return entry[0], entry[1]


if __name__ == "__main__":
    tasks = LazyMinHeap[str]()
    cancelled_token = tasks.push(5, "cancelled")
    tasks.push(1, "ready")

    print(tasks.pop())                    # (1, 'ready')
    print(tasks.delete(cancelled_token))  # True
    print(tasks.pop())                    # raises IndexError: pop from empty heap

Example Walkthrough

Step Operation Heap root Result
1 Push priority 5, "cancelled" "cancelled" Token 0 is live
2 Push priority 1, "ready" "ready" Token 1 becomes the root
3 pop() "ready" Returns (1, "ready")
4 Delete token 0 "cancelled" Entry remains physically present but is marked stale
5 pop() Empty Discards the stale entry, then raises IndexError

Common Pitfalls

  • Duplicate values: Do not use the item itself as its deletion identifier; use a unique token.

  • Mutable entries: Insert an immutable snapshot or immutable object because changing a stored value can violate heap ordering.

  • Memory growth: Deleting many entries without popping them leaves stale entries in the heap; periodically rebuild it when necessary.

  • Edge cases: Empty heaps raise IndexError, negative priorities work normally, and equal priorities are ordered by their unique tokens.

  • Common follow-up: Interviewers often ask how lazy deletion compares with indexed-heap deletion and how stale entries are periodically cleaned up.

10

What does heapify do in a binary heap?

Heapify transforms an array into a valid binary heap by restoring the heap property at every parent node. It is used to build heaps efficiently and to repair a heap after bulk modifications, while individual insertions and removals use smaller sift operations.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Heapify Works

A binary heap is a complete binary tree stored in an array:

  • The left child of index index is at 2 * index + 1.

  • The right child is at 2 * index + 2.

  • The parent is at (index - 1) // 2.

  • A min-heap requires every parent to be less than or equal to its children.

Heapify processes internal nodes from the bottom upward. For each node, it compares the node with its children and moves the smaller child upward until the subtree satisfies the heap property.

This bottom-up strategy takes O(n) time rather than O(n log n). Nodes near the bottom have little work, while only a small number of nodes can sift through many levels; the total work is proportional to n.

For a max-heap, reverse the comparisons so the largest child moves upward.

Where It Is Used

Operation or scenario Method used Time
Build a heap from an unsorted array Bottom-up heapify O(n) best, average, and worst
Insert one value Sift up O(1) best; O(log n) average and worst; O(log n) amortized
Remove the root Sift down O(1) best; O(log n) average and worst
Inspect the root Direct array access O(1)
Repair a heap after bulk changes Re-run heapify O(n)

In Python, heapq.heapify(values) performs the equivalent operation for a min-heap and modifies the list in place. Standard heapq.heappush and heapq.heappop do not call heapify for every operation; they use targeted sift operations, which are much cheaper.

Step-by-Step Example

For the min-heap input [3, 1, 4, 1, 5, 9]:

  1. Process index 2 (value 4): its only child 9 is larger, so nothing moves.

  2. Process index 1: its value 1 is already no greater than its children.

  3. Process the root 3: swap it with the smaller child 1.

  4. Continue sifting the displaced value until the heap property holds.

The result is [1, 1, 4, 3, 5, 9].

Code Example

The following implementation demonstrates the core heap operations rather than relying only on heapq:

def sift_down(heap: list[int], root: int, size: int) -> None:
    """Restore the min-heap property below root within the first size items."""
    while True:
        left = 2 * root + 1
        right = 2 * root + 2
        smallest = root

        if left < size and heap[left] < heap[smallest]:
            smallest = left
        if right < size and heap[right] < heap[smallest]:
            smallest = right

        if smallest == root:
            return

        heap[root], heap[smallest] = heap[smallest], heap[root]
        root = smallest


def heapify(values: list[int]) -> list[int]:
    """Transform values into a min-heap in place and return it."""
    for root in range(len(values) // 2 - 1, -1, -1):
        sift_down(values, root, len(values))
    return values


def heap_push(heap: list[int], value: int) -> None:
    """Insert value into a min-heap and restore the heap property."""
    heap.append(value)
    index = len(heap) - 1

    while index > 0:
        parent = (index - 1) // 2
        if heap[parent] <= value:
            break

        heap[index] = heap[parent]
        index = parent

    heap[index] = value


def heap_pop(heap: list[int]) -> int:
    """Remove and return the minimum value from a non-empty min-heap."""
    if not heap:
        raise IndexError("pop from an empty heap")

    minimum = heap[0]
    last_value = heap.pop()

    if heap:
        heap[0] = last_value
        sift_down(heap, 0, len(heap))

    return minimum


if __name__ == "__main__":
    values = [3, 1, 4, 1, 5, 9]
    print(heapify(values))       # [1, 1, 4, 3, 5, 9]
    heap_push(values, 0)
    print(values)                # [0, 1, 1, 3, 5, 9, 4]
    print(heap_pop(values))      # 0
    print(values)                # [1, 3, 1, 4, 5, 9]

Common Pitfalls

  • Complexity confusion: Repeatedly inserting n elements costs O(n log n); one bottom-up heapify costs O(n).

  • Wrong indexing: Array-based heaps use 2 * index + 1, 2 * index + 2, and (index - 1) // 2.

  • Confusing heapify with sorting: Heapify creates only a partial ordering; it does not sort the entire array.

  • Unnecessary reheapification: Calling heapify after each insertion or removal changes the operation from O(log n) to O(n).

  • Edge cases: Empty input is valid for heapify; popping an empty heap raises IndexError. One-element heaps, duplicates, and negative values work normally. An already sorted array may already satisfy min-heap ordering. Disconnected graphs and cycles are not applicable to heaps.

  • Space accounting: The iterative implementation uses O(1) auxiliary space, including no recursion stack. The mutated input array occupies O(n) space if the input itself is counted.

11

How does Heap Sort order elements using a heap?

Heap Sort is a comparison-based sorting algorithm that uses a max-heap to repeatedly move the largest remaining element into its final position. It runs in O(n log n) time in the best, average, and worst cases and sorts the input in place with O(1) auxiliary space.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A binary heap is a complete binary tree stored in an array. In a zero-based array, the children of index i are 2i + 1 and 2i + 2, while its parent is (i - 1) // 2.

Heap Sort uses these steps:

  1. Build a max-heap, where every parent is at least as large as its children.

  2. Swap the root, which contains the largest element, with the last element of the unsorted portion.

  3. Exclude that final position from the heap.

  4. Restore the max-heap property by sifting the root downward.

  5. Repeat until only one unsorted element remains.

The sorted portion grows from the end of the array toward the beginning.

Complexity

Operation Best Average Worst Reason
Build max-heap O(n) O(n) O(n) Nodes near the leaves require little work; the total across all levels is O(n), not O(n log n).
Repeated extraction O(n log n) O(n log n) O(n log n) Each of the n - 1 extractions can sift an element down O(log n) levels.
Total time O(n log n) O(n log n) O(n log n) Heap construction is O(n), and extraction dominates.
Auxiliary space O(1) O(1) O(1) The implementation is iterative and uses no recursion stack.

The input list occupies O(n) storage, but that storage is not additional working space. The algorithm mutates the existing list.

Step-by-Step Example

For [4, 1, 3, 2]:

Stage Array
Initial array [4, 1, 3, 2]
Build max-heap [4, 2, 3, 1]
Move 4 to the end [1, 2, 3, 4]
Restore the heap [3, 2, 1, 4]
Move 3 to its final position [1, 2, 3, 4]
Restore the heap [2, 1, 3, 4]
Move 2 to its final position [1, 2, 3, 4]

Code Example

def heap_sort(values: list[int]) -> list[int]:
    """Sort integers in ascending order in place and return the list."""

    def sift_down(root: int, heap_size: int) -> None:
        while True:
            left = 2 * root + 1
            right = 2 * root + 2
            largest = root

            if left < heap_size and values[left] > values[largest]:
                largest = left

            if right < heap_size and values[right] > values[largest]:
                largest = right

            if largest == root:
                return

            values[root], values[largest] = values[largest], values[root]
            root = largest

    heap_size = len(values)

    # Build a max-heap from the bottom up.
    for root in range(heap_size // 2 - 1, -1, -1):
        sift_down(root, heap_size)

    # Repeatedly move the maximum into its final position.
    for end in range(heap_size - 1, 0, -1):
        values[0], values[end] = values[end], values[0]
        sift_down(0, end)

    return values


numbers = [4, -1, 3, 3, 2, 0]
print(heap_sort(numbers))  # [-1, 0, 2, 3, 3, 4]

Common Pitfalls and Interview Tips

  • Wrong child indices: With zero-based indexing, children are 2i + 1 and 2i + 2, not 2i and 2i + 1.

  • Incorrect heap boundary: After moving the maximum, sift down only within the reduced heap; the sorted suffix must be excluded.

  • Input mutation: This implementation sorts the original list. Copy it first if the caller needs the original ordering.

  • Edge cases: Empty and one-element lists are already sorted. Duplicates and negative values are handled naturally.

  • Stability: Heap Sort is not stable because swapping elements can change the relative order of equal keys.

  • Practical use: Python’s built-in list.sort() is usually preferable because it is highly optimized and typically faster, though it also uses O(n) auxiliary space.

12

How does Heap Sort compare to Quick Sort for speed and memory usage?

Heap Sort and Quick Sort are both comparison-based sorting algorithms, but they differ in their performance guarantees and memory usage. Heap Sort consistently runs in O(n log n) time and can use only O(1) auxiliary space, while Quick Sort is often faster in practice but has an O(n²) worst case and typically uses O(log n) additional space for its recursion stack.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How They Work

  • Heap Sort:

  • Builds a max-heap from the input.

  • Repeatedly swaps the largest element at the heap root with the final unsorted element.

  • Reduces the heap size and restores the heap property.

  • The final array is sorted in ascending order.

Building the heap is O(n), not O(n log n), because most nodes are near the bottom of the tree and have small subtrees. The total work is proportional to the sum of the heights of all heap levels. Each of the n removals costs O(log n).

  • Quick Sort:

  • Selects a pivot element.

  • Partitions the array so elements less than the pivot are on one side and greater elements are on the other.

  • Recursively sorts the two partitions.

A good pivot produces balanced partitions, giving O(n log n) average performance. Repeatedly selecting the smallest or largest element creates highly unbalanced partitions and causes the O(n²) worst case.

Complexity Comparison

Algorithm Best Time Average Time Worst Time Auxiliary Space Key Property
Heap Sort O(n log n) O(n log n) O(n log n) O(1) with an iterative heap operation Predictable time and space
Quick Sort O(n log n) O(n log n) O(n²) O(log n) average stack space; O(n) worst-case stack space Often fast in practice

The space figures count the algorithm’s temporary storage and recursion stack, but do not count the input array itself. If the input array is included, both algorithms use O(n) total storage.

Quick Sort’s partitioning operation normally needs only O(1) extra space, but recursive calls add the stack cost. Heap Sort can avoid recursion entirely by implementing heap adjustments iteratively.

Speed in Practice

  • Quick Sort is often faster on average because partitioning is cache-friendly and tends to involve fewer comparisons and swaps than repeated heap adjustments.

  • Heap Sort has a stronger worst-case guarantee: it never degrades beyond O(n log n).

  • Actual performance depends on the implementation, data layout, pivot strategy, and processor cache behavior.

  • A production sorting algorithm such as introsort combines Quick Sort’s typical speed with a fallback to Heap Sort when recursion becomes too deep.

  • Both algorithms are generally not stable, so equal elements may be reordered.

Memory Usage

Heap Sort is usually the better choice when minimizing auxiliary memory is important:

  • An iterative Heap Sort implementation uses O(1) auxiliary space.

  • A recursive Quick Sort implementation uses approximately O(log n) stack space with balanced partitions.

  • A degenerate Quick Sort partition can produce O(n) recursion depth and therefore O(n) auxiliary stack space.

  • Sorting a copy of the input would require O(n) additional storage regardless of the algorithm.

For very large datasets, in-place Heap Sort can therefore avoid recursion and extra allocation, although its runtime may still be higher than a well-implemented Quick Sort.

Interview Tips

  • Mention O(n log n) as Heap Sort’s best, average, and worst-case time.

  • Mention Quick Sort’s O(n log n) average case and O(n²) worst case.

  • Distinguish O(1) auxiliary space from total memory usage, which includes the input array.

  • A common follow-up asks how Quick Sort’s worst case is prevented: use randomized pivots, median-of-three selection, three-way partitioning for duplicates, or introsort.

  • Another follow-up asks why Heap Sort’s build-heap phase is O(n): the total cost depends on the sum of all subtree heights rather than performing an O(log n) operation independently for every element.

13

How to merge k sorted arrays using a heap?

Merging k sorted arrays is a classic algorithmic problem where a min-heap is used to efficiently combine multiple sorted lists into a single sorted sequence. By maintaining only the smallest unprocessed element from each array in the heap, the algorithm avoids the overhead of sorting all elements at once.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The core idea is to treat the problem as a “k-way merge” where the heap acts as a priority queue for the current front of each array.

  1. Initialize: Push the first element of every non-empty array into the min-heap. Each heap entry stores the value along with the array index and element index so the next value can be located later.

  2. Extract Minimum: Pop the smallest value from the heap and append it to the result list.

  3. Replace: If the popped element had a successor in its original array, push that successor into the heap.

  4. Repeat: Continue steps 2 and 3 until the heap is empty.

This ensures that at any point, the heap contains at most one candidate from each of the k arrays, and the smallest candidate is always available in O(1) time.

Example Walkthrough

Consider merging three arrays: [[1, 4], [2, 5], [3, 6]].

  1. Initial heap: push first elements → [(1,0,0), (2,1,0), (3,2,0)].

  2. Pop 1 (from array 0, index 0) → result [1]. Push next from array 0: 4 → heap [(2,1,0), (3,2,0), (4,0,1)].

  3. Pop 2 (from array 1, index 0) → result [1,2]. Push next from array 1: 5 → heap [(3,2,0), (4,0,1), (5,1,1)].

  4. Pop 3 (from array 2, index 0) → result [1,2,3]. Push next from array 2: 6 → heap [(4,0,1), (5,1,1), (6,2,1)].

  5. Pop 4 → result [1,2,3,4]. Array 0 exhausted.

  6. Pop 5 → result [1,2,3,4,5]. Array 1 exhausted.

  7. Pop 6 → result [1,2,3,4,5,6]. Array 2 exhausted. Heap empty → done.

Complexity and Alternatives

The heap approach is optimal compared to a naive concatenation sort.

Approach Time Complexity Space Complexity When to Use
Min-Heap (Optimal) O(N log k) O(k) Large k or streaming data
Concatenate & Sort O(N log N) O(N) Small k or one-time batch
  • Time: O(N log k), where N is the total number of elements across all arrays and k is the number of arrays. Every element is pushed and popped exactly once, and each heap operation costs O(log k). Best, average, and worst cases are identical.

  • Space: O(k) auxiliary space for the heap. The output array is O(N) but typically excluded from auxiliary space analysis.

Code Example

This implementation uses heapq to manage the min-heap. It handles empty inputs, empty sub-arrays, and duplicate values by storing (value, array_index, element_index) tuples.

import heapq
from typing import List

def merge_k_sorted_arrays(arrays: List[List[int]]) -> List[int]:
    """
    Merges k sorted arrays into a single sorted array using a min-heap.
    """
    if not arrays:
        return []

    result = []
    heap = []

    # Push the first element of each non-empty array
    for i, arr in enumerate(arrays):
        if arr:
            heapq.heappush(heap, (arr[0], i, 0))

    # Extract min and push the next element from the same array
    while heap:
        value, arr_idx, elem_idx = heapq.heappop(heap)
        result.append(value)

        if elem_idx + 1 < len(arrays[arr_idx]):
            next_val = arrays[arr_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, arr_idx, elem_idx + 1))

    return result

# Example call:
# arrays = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
# print(merge_k_sorted_arrays(arrays))  # Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Common Pitfalls

  • Empty Arrays: Failing to check if an array is empty before pushing its first element causes an IndexError. Always validate if arr:.

  • Missing Successor Push: A common logic error is popping the min value but forgetting to push the next element from that specific array, which truncates the result.

  • Tuple Comparison: If you store only (value, index) and values are equal, Python compares the index. This is safe. However, if you store only values, equal values are fine, but you lose track of the source array. Always store enough context to retrieve the next element.

  • Input Mutation: Do not modify the input arrays in place; the algorithm should return a new list.

  • Follow-up: Interviewers often ask how to merge two sorted arrays in O(1) space or how to find the Kth smallest element in a sorted matrix, which uses the same heap logic.

14

Implement a heap with O(1) Find-Max and Find-Min.

A dual-heap structure stores every value in both a min-heap and a max-heap, allowing Find-Min and Find-Max to read the respective roots in O(1) time. Insertion takes O(log n) in the worst case because the new value must be sifted up in both heaps.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • A binary heap is a complete binary tree stored in an array. For index i, the children are at 2i+1 and 2i+2, and the parent is at (i-1)//2.

  • min_heap is a min-heap, so its root contains the smallest value.

  • max_heap is a max-heap, so its root contains the largest value.

  • insert appends the value to both arrays and performs the appropriate sift-up operation.

  • find_min and find_max directly inspect index 0, making both operations O(1).

  • All values must be mutually comparable; unsupported comparisons raise Python’s usual TypeError.

  • A standard heap push or root removal is O(log n) in the worst case. Bulk heap construction is O(n): the number of nodes with height h is O(n / 2^h), and summing their O(h) sift-down work gives O(n), rather than performing O(log n) work for every element independently.

Complexity

Operation Best Average Worst Reason
insert O(1) O(log n) upper bound O(log n) Sift-up in two heaps; the actual average depends on how far values move
find_min O(1) O(1) O(1) Reads the min-heap root
find_max O(1) O(1) O(1) Reads the max-heap root

The structure uses O(n) total space for the two heaps. It is iterative, so the recursion stack uses O(1) additional space; any separate collection supplied by the caller is not included.

Step-by-Step Example

Action min_heap max_heap Visible extremes
Insert 5 [5] [5] Min 5, max 5
Insert 3 [3, 5] [5, 3] Min 3, max 5
Insert 9 [3, 5, 9] [9, 3, 5] Min 3, max 9

Code Example

from typing import Any


class MinMaxHeap:
    """Maintain O(1) minimum and maximum lookups using two binary heaps."""

    def __init__(self) -> None:
        self.min_heap: list[Any] = []
        self.max_heap: list[Any] = []

    def _sift_up_min(self, heap: list[Any], index: int) -> None:
        while index > 0:
            parent = (index - 1) // 2
            if heap[index] < heap[parent]:
                heap[index], heap[parent] = heap[parent], heap[index]
                index = parent
            else:
                break

    def _sift_down_min(self, heap: list[Any], index: int) -> None:
        while 2 * index + 1 < len(heap):
            left = 2 * index + 1
            right = left + 1
            smallest = left
            if right < len(heap) and heap[right] < heap[left]:
                smallest = right
            if heap[smallest] < heap[index]:
                heap[index], heap[smallest] = heap[smallest], heap[index]
                index = smallest
            else:
                break

    def _sift_up_max(self, heap: list[Any], index: int) -> None:
        while index > 0:
            parent = (index - 1) // 2
            if heap[index] > heap[parent]:
                heap[index], heap[parent] = heap[parent], heap[index]
                index = parent
            else:
                break

    def _sift_down_max(self, heap: list[Any], index: int) -> None:
        while 2 * index + 1 < len(heap):
            left = 2 * index + 1
            right = left + 1
            largest = left
            if right < len(heap) and heap[right] > heap[left]:
                largest = right
            if heap[largest] > heap[index]:
                heap[index], heap[largest] = heap[largest], heap[index]
                index = largest
            else:
                break

    def insert(self, value: Any) -> None:
        self.min_heap.append(value)
        self._sift_up_min(self.min_heap, len(self.min_heap) - 1)

        self.max_heap.append(value)
        self._sift_up_max(self.max_heap, len(self.max_heap) - 1)

    def find_min(self) -> Any:
        if not self.min_heap:
            raise ValueError("Heap is empty")
        return self.min_heap[0]  # Minimum is always at the root.

    def find_max(self) -> Any:
        if not self.max_heap:
            raise ValueError("Heap is empty")
        return self.max_heap[0]  # Maximum is always at the root.


heap = MinMaxHeap()
heap.insert(5)
heap.insert(3)
heap.insert(9)

print(heap.find_min())  # Output: 3
print(heap.find_max())  # Output: 9

Common Pitfalls

  • Empty input: Both lookup methods raise ValueError rather than indexing an empty list.

  • One element: The same value is returned as both the minimum and maximum.

  • Duplicates: Both heaps retain every occurrence. Future deletion would need stable identifiers to match the correct duplicate across heaps.

  • Negative numbers: Comparisons work normally because the implementation does not assume non-negative values.

  • Already sorted input: Inserting sorted values still produces valid heaps and correct extremes.

  • Graph-specific cases: Disconnected graphs and cycles are not applicable because this structure contains no graph.

  • Deletion: The minimal implementation intentionally omits deletion. Supporting it efficiently requires a way to identify matching elements across the two heaps, typically with stable IDs and lazy invalidation.

15

Where are binary heaps used in practical applications?

A binary heap is a complete binary tree, usually stored in an array, that efficiently maintains the smallest or largest element. It powers priority queues and is used in scheduling, shortest-path algorithms, top-K selection, stream processing, and other problems requiring repeated minimum or maximum extraction.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Heap Properties and Complexity

A binary heap supports the following operations:

  • Peek: O(1) time because the root is directly accessible.

  • Push: O(log n) time because the new element moves upward until the heap property is restored.

  • Pop: O(log n) time because the root is replaced and sifted downward through the tree’s O(log n) height.

  • Heapify: O(n) time because sift-down work decreases across the tree’s levels and sums to O(n), rather than O(n log n).

  • Space: O(n) to store the heap. These deterministic operations have the same best, average, and worst-case bounds. Iterative implementations need no recursion stack.

Python’s heapq implements a min-heap. For a max-heap, negate numeric values or use (-priority, item) tuples. If equal priorities could cause incomparable items to be compared, use (-priority, counter, item) so the counter breaks ties first.

Common Applications

Application How the heap is used Time complexity Auxiliary space
Priority queue Stores tasks by priority and selects the next task O(log n) insert/extract; O(1) peek O(n) queued tasks
Dijkstra’s algorithm Extracts the vertex with the smallest tentative distance Lazy: O(V + E log(E + 1)); indexed decrease-key: O((V + E) log(V + 1)) Lazy: O(V + E); indexed: O(V)
Top-K elements Maintains the K best candidates seen so far O(n log k) for 1 < k ≤ n O(k)
K-way merge Stores the next element from each sorted list O(N log(r + 1)) O®
Streaming median Uses two heaps to maintain the lower and upper halves O(log n) insertion; O(1) median lookup O(n) retained values
Task scheduling Selects the highest-priority runnable task O(n log n) for n extractions O(n) queued tasks

Here, V is the number of vertices, E the number of edges, N the total number of merged elements, and r the number of lists. Auxiliary space excludes the original graph, lists, or stream unless noted. Including Dijkstra’s input graph makes its total space O(V + E) in either implementation.

Dijkstra requires non-negative edge weights. Disconnected graphs require an explicit unreachable-distance value such as infinity, while cycles are valid when their edge weights are non-negative.

Worked Example: Top-K Elements

Keep a min-heap of at most K candidates. Whenever a new value exceeds the heap’s smallest retained value, replace that root.

For [7, 2, 9, 4, 1, 8] with K = 3:

Value processed Retained candidates, shown as a set
7 {7}
2 {2, 7}
9 {2, 7, 9}
4 {4, 7, 9}
1 {4, 7, 9}
8 {7, 8, 9}

The selected values are 9, 8, and 7. The heap itself is not necessarily sorted; sorting is only needed when ordered output is required.

For 1 < K <= n, the algorithm takes O(n log k) time and O(k) space. For K = 1, it takes O(n) time and O(1) space. If K >= n, all n values are selected and ordering them takes O(n log n) worst-case time. Empty input or a nonpositive K produces an empty result. One-element inputs, duplicates, negative values, and already sorted inputs are handled without changing these asymptotic bounds.

Common Pitfalls and Interview Tips

  • Choosing the wrong heap order: heapq is a min-heap; negate values or reverse priority signs carefully for a max-heap.

  • Incorrect complexity claims: Push and pop are O(log n), but heap construction is O(n), not O(n log n).

  • Ignoring duplicates: Top-K operations normally retain duplicate values as separate elements.

  • Unnecessary sorting: A heap supports incremental selection; sorting the entire input is often more expensive.

  • Using a heap for simple frequency counting: Counter updates are O(1) average and O(n) worst case per operation, so counting n items is O(n) average and O(n²) worst case under pathological hash collisions.

  • Arbitrary updates: Python’s heapq does not provide efficient updates to an arbitrary element; an indexed heap is usually needed.

  • Common follow-ups: Interviewers may ask about two-heap median maintenance, Dijkstra’s algorithm, K-way merging, or how to support updates to arbitrary heap elements.

16

How does a min-heap support Huffman coding?

A min-heap lets Huffman coding repeatedly select the two symbols or subtrees with the smallest frequencies. These are merged into a new node whose frequency is their sum, and the merged node is inserted back into the heap.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Role of the Min-Heap

Huffman coding builds a binary tree where:

  • Leaves represent the original symbols.

  • Internal nodes represent merged groups of symbols.

  • The two least-frequent nodes are always siblings.

  • Left and right branches are assigned binary codes such as 0 and 1.

The min-heap stores nodes ordered by frequency, so the two smallest nodes can be removed efficiently.

Algorithm

  1. Count the frequency of every symbol.

  2. Create one tree node for each symbol and insert it into a min-heap.

  3. While more than one node remains:

  4. Remove the two nodes with the smallest frequencies.

  5. Create a parent node whose frequency is their sum.

  6. Insert the parent node back into the heap.

  7. Traverse the resulting tree from the root to its leaves.

  8. Record the path to each leaf as that symbol’s binary code.

The heap is an array-backed complete binary tree. For an index i, its children are at 2i + 1 and 2i + 2, and its parent is at (i - 1) // 2.

Example Walkthrough

For "aabbbcccc", the frequencies are:

Symbol Frequency
a 2
b 3
c 4

The construction proceeds as follows:

  1. Remove a(2) and b(3); create a parent with frequency 5.

  2. Remove c(4) and the parent (5); create the root with frequency 9.

  3. Assign 0 to the left branch and 1 to the right branch.

Using the implementation below, one valid result is:

a -> 11
b -> 10
c -> 0

The codes are prefix-free: no symbol’s code is a prefix of another symbol’s code.

Complexity

Let n be the number of distinct symbols and m the length of the input text.

  • Frequency counting: O(m) average time.

  • Heap construction: O(n) time using bottom-up heapification. Heapification is linear because most nodes are near the bottom and require little or no movement.

  • Merging: There are n - 1 merges, and each performs heap removals and an insertion costing O(log n) each, for O(n log n) total time.

  • Tree traversal: O(n) time.

  • Overall time: O(m + n log n) average time. The construction itself is O(n log n) in the best, average, and worst cases because the number of merges is fixed.

  • Space: O(n) auxiliary space for the heap, tree, and traversal stack. The input text is not counted. The implementation is iterative, so it does not consume recursion-stack space.

Approach Time Space When to use
Repeatedly scan for the two smallest nodes O(n²) O(n) Very small inputs or a simple educational implementation
Min-heap-based Huffman construction O(n log n) O(n) Standard Huffman coding and interview solutions

Code Example

from __future__ import annotations

from collections import Counter
from dataclasses import dataclass


@dataclass(eq=False)
class _HuffmanNode:
    frequency: int
    symbol: str
    left: _HuffmanNode | None = None
    right: _HuffmanNode | None = None
    code: str = ""

    def __lt__(self, other: _HuffmanNode) -> bool:
        if self.frequency != other.frequency:
            return self.frequency < other.frequency
        return self.symbol < other.symbol


class _MinHeap:
    def __init__(self, items: list[_HuffmanNode]) -> None:
        self._items = items[:]

        # Build the heap bottom-up in O(n).
        for index in range(len(self._items) // 2 - 1, -1, -1):
            self._sift_down(index)

    def __len__(self) -> int:
        return len(self._items)

    def push(self, item: _HuffmanNode) -> None:
        self._items.append(item)
        self._sift_up(len(self._items) - 1)

    def pop(self) -> _HuffmanNode:
        if not self._items:
            raise IndexError("pop from an empty heap")

        minimum = self._items[0]
        last_item = self._items.pop()

        if self._items:
            self._items[0] = last_item
            self._sift_down(0)

        return minimum

    def _sift_up(self, index: int) -> None:
        while index > 0:
            parent_index = (index - 1) // 2
            if not self._items[index] < self._items[parent_index]:
                break

            self._items[index], self._items[parent_index] = (
                self._items[parent_index],
                self._items[index],
            )
            index = parent_index

    def _sift_down(self, index: int) -> None:
        while True:
            left_index = 2 * index + 1
            if left_index >= len(self._items):
                break

            right_index = left_index + 1
            smaller_index = left_index

            if (
                right_index < len(self._items)
                and self._items[right_index] < self._items[left_index]
            ):
                smaller_index = right_index

            if not self._items[index] < self._items[smaller_index]:
                break

            self._items[index], self._items[smaller_index] = (
                self._items[smaller_index],
                self._items[index],
            )
            index = smaller_index


def build_huffman_codes(text: str) -> dict[str, str]:
    """Return prefix-free Huffman codes for the characters in text."""
    frequencies = Counter(text)
    if not frequencies:
        raise ValueError("text must contain at least one character")

    heap = _MinHeap(
        [
            _HuffmanNode(frequency=frequency, symbol=symbol)
            for symbol, frequency in frequencies.items()
        ]
    )

    while len(heap) > 1:
        left = heap.pop()
        right = heap.pop()

        parent = _HuffmanNode(
            frequency=left.frequency + right.frequency,
            symbol="",
            left=left,
            right=right,
        )
        heap.push(parent)

    root = heap.pop()

    # A one-symbol alphabet receives one bit.
    if root.left is None:
        return {root.symbol: "0"}

    codes: dict[str, str] = {}
    stack: list[tuple[_HuffmanNode, str]] = [(root, "")]

    while stack:
        node, prefix = stack.pop()

        if node.left is None:
            codes[node.symbol] = prefix
            continue

        # Every internal node created by the merge step has two children.
        stack.append((node.right, prefix + "1"))
        stack.append((node.left, prefix + "0"))

    return dict(sorted(codes.items()))


print(build_huffman_codes("aabbbcccc"))
# {'a': '11', 'b': '10', 'c': '0'}

Common Pitfalls

  • Empty input: The function raises ValueError; there is no meaningful code for an empty alphabet.

  • One distinct symbol: It receives the conventional code "0".

  • Duplicate occurrences: They are counted as one symbol with a higher frequency.

  • Tie-breaking: Different valid Huffman trees can result when frequencies are equal; interviewers should accept any valid prefix-free codes.

  • Negative frequencies: They cannot arise from text frequencies. A weighted-symbol API should reject them.

  • Input order: Already sorted, reverse-sorted, or arbitrary input does not change the asymptotic construction cost.

  • Implementation detail: Avoid recursive tree traversal because highly skewed trees can exceed Python’s default recursion limit.

17

How are heaps used in real-time task scheduling?

Heaps are used in real-time scheduling to implement priority queues, allowing the system to efficiently select the next task to execute based on urgency.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Why Heaps are Ideal

Real-time systems must make scheduling decisions quickly and predictably. A heap provides the necessary performance characteristics for a priority queue: - Time Complexity: Insertion (heappush) and removal (heappop) are O(log n) because the heap property requires re-balancing along the tree height. Peeking at the highest priority task is O(1) since it is always at the root. - Space Complexity: O(n) to store the tasks in the underlying array. This includes the space for the input tasks themselves. - Predictability: Unlike a sorted list, which requires O(n) insertion, a heap maintains order with logarithmic cost, ensuring bounded latency for critical tasks.

Common Scheduling Algorithms

The choice between a min-heap and a max-heap depends on the scheduling policy:

Algorithm Heap Type Key Priority Rule
Earliest Deadline First (EDF) Min-heap Deadline Smallest deadline first
Rate Monotonic (RMS) Max-heap Frequency Highest frequency first
  • Python heapq: This library implements a min-heap. To simulate a max-heap, you negate the priority values or use tuples like (-priority, item).

  • Internal Structure: A binary heap is a complete binary tree stored in an array. Children of index i are at 2i+1 and 2i+2, and the parent is at (i-1)//2.

Code Example

The following example simulates a scheduler that processes tasks by their deadlines using a min-heap.

import heapq
from typing import List, Tuple

def schedule_tasks(tasks: List[Tuple[int, int, str]]) -> List[str]:
    """
    Simulates a real-time scheduler using a min-heap.
    Tasks are tuples of (deadline, priority, name).
    Returns the order in which tasks are executed.
    """
    heap: List[Tuple[int, int, str]] = []
    for deadline, priority, name in tasks:
        heapq.heappush(heap, (deadline, priority, name))

    scheduled: List[str] = []
    while heap:
        deadline, priority, name = heapq.heappop(heap)
        scheduled.append(name)
    return scheduled

# Example: Tasks with deadlines and priorities
# Output: ['TaskB', 'TaskC', 'TaskA']
print(schedule_tasks([(10, 1, 'TaskA'), (5, 2, 'TaskB'), (7, 3, 'TaskC')]))

Interview Tips

  • Follow-up: Interviewers often ask how to handle decrease-key operations (when a task’s deadline changes). In Python, this is usually done via lazy deletion: mark the old entry as invalid and push the new one.

  • Edge Cases: Always handle empty input and duplicate deadlines. In the code above, ties are broken by the secondary priority value in the tuple.

  • Language Specifics: If asked about C++ or Java, mention std::priority_queue or java.util.PriorityQueue, which also use binary heaps.

  • Real-World Context: Be ready to discuss preemption, where a higher-priority task interrupts a running lower-priority task, and how heaps facilitate the quick rescheduling.

18

How to find median of data stream using heaps

The most efficient solution is the Two-Heap Approach, which maintains a max-heap for the lower half of the numbers and a min-heap for the upper half. By keeping the heaps balanced, the median can be retrieved in constant time while new numbers are added in logarithmic time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Split the stream into two halves: a max-heap (lower) containing the smaller numbers and a min-heap (upper) containing the larger numbers.

  • Maintain the invariant that every element in lower is less than or equal to every element in upper.

  • Balance the heaps so that len(lower) is either equal to len(upper) or exactly one greater. This ensures the median is always at the root of one of the heaps.

  • In Python, heapq implements a min-heap. To create a max-heap, store negated values (e.g., -num).

Complexity Analysis

  • addNum: O(log n) time because inserting into a heap requires O(log n) comparisons. Space is O(1) auxiliary.

  • findMedian: O(1) time because it only accesses the root of the heaps.

  • Overall Space: O(n) to store all elements in the two heaps.

Step-by-Step Example

Stream: [5, 15, 1, 3]

  1. Add 5: lower=[5], upper=[]. Median is 5.

  2. Add 15: Move 5 to upper. lower=[5], upper=[15]. Median is (5 + 15) / 2 = 10.

  3. Add 1: Move 5 to upper, then move min of upper (5) back to lower. lower=[1, 5], upper=[15]. Median is 5.

  4. Add 3: Move 5 to upper. lower=[1, 3], upper=[5, 15]. Median is (3 + 5) / 2 = 4.

Code Example

import heapq
from typing import List

class MedianFinder:
    """Maintains two heaps to find the median of a data stream."""

    def __init__(self) -> None:
        self.lower: List[int] = []  # Max-heap (stores negated values)
        self.upper: List[int] = []  # Min-heap

    def addNum(self, num: int) -> None:
        """Inserts a number into the data structure."""
        heapq.heappush(self.lower, -num)
        # Move the largest element of the lower half to the upper half
        heapq.heappush(self.upper, -heapq.heappop(self.lower))
        # Rebalance: lower can have at most one more element than upper
        if len(self.lower) < len(self.upper):
            heapq.heappush(self.lower, -heapq.heappop(self.upper))

    def findMedian(self) -> float:
        """Returns the current median of the data stream."""
        if not self.lower and not self.upper:
            raise ValueError("Stream is empty")
        if len(self.lower) > len(self.upper):
            return -self.lower[0]
        return (-self.lower[0] + self.upper[0]) / 2

# Example usage:
# mf = MedianFinder()
# mf.addNum(5); mf.addNum(15); mf.addNum(1); mf.addNum(3)
# print(mf.findMedian())  # Output: 4.0

Common Pitfalls

  • Forgetting to negate: heapq is a min-heap, so failing to store -num in the lower heap breaks the max-heap property.

  • Skipping rebalancing: If upper grows larger than lower, the median will be taken from the wrong heap.

  • Integer division: Use / instead of // to ensure the median is a float when the average is not an integer.

  • Empty stream: Always handle the case where findMedian is called before any numbers are added.

  • Follow-up: Interviewers often ask how to handle a stream of integers that cannot fit in memory, or how to find the median of a sliding window.

19

Why are heaps preferable to sorted arrays for dynamic data?

Binary heaps are preferable when the most important operations are inserting elements and repeatedly accessing or removing the minimum or maximum. Unlike sorted arrays, they support these priority-queue operations efficiently without shifting every subsequent element.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How They Work

A binary heap is a complete binary tree commonly stored in an array:

  • The root at index 0 contains the minimum element in a min-heap.

  • The children of index i are at 2i + 1 and 2i + 2.

  • The parent of index i is at (i - 1) // 2.

  • A sorted array stores all elements in ascending or descending order.

The heap maintains only a partial ordering: every parent is no greater than its children in a min-heap. It does not maintain the complete ordering required by a sorted array.

Complexity Comparison

Operation Binary heap Sorted array
Build from existing data O(n) with heapify O(n log n) with comparison sorting
Read minimum or maximum O(1) O(1)
Insert an element O(1) best, O(log n) average and worst O(1) when appended at the sorted end; O(n) otherwise
Remove minimum or maximum O(1) best, O(log n) average and worst O(1) at the array’s end; O(n) at the front because remaining elements must shift
Search for an arbitrary value O(n) O(log n) with binary search
Traverse in sorted order O(n log n) O(n)
Space O(n) O(n)

For heap insertion and removal, the best case occurs when no reordering is necessary. The average and worst cases require moving the element through the heap’s height, which is O(log n).

Building a heap is O(n), not O(n log n), because most nodes are near the bottom and have very little work. Summing the number of possible sift-down steps across all levels gives a geometric series bounded by O(n).

Main Advantages

  • Efficient updates: Insertion and removal take O(log n), avoiding the O(n) shifting often required by sorted arrays.

  • Constant-time priority access: The minimum or maximum is always available at the root in O(1).

  • Suitable for dynamic workloads: Heaps work well when elements arrive continuously and the highest-priority (smallest or largest) item must be removed next.

  • No full sorting requirement: A heap stores only enough ordering to identify the next extreme element.

  • Compact representation: A complete binary heap can be stored in an array without pointers.

Typical uses include task scheduling, Dijkstra’s algorithm, merge procedures, streaming top-K selection, and maintaining a median with two heaps.

Limitations and When Sorted Arrays Win

A heap does not provide the complete ordering offered by a sorted array:

  • Finding an arbitrary element requires O(n) scanning.

  • Enumerating elements in sorted order requires additional work, usually O(n log n).

  • Range queries and predecessor/successor searches are not efficient without extra structures.

  • A balanced tree map is usually better when all keys must remain searchable and ordered.

Therefore, heaps are advantageous for priority queues, not as a general-purpose replacement for sorted arrays.

Common Pitfalls

  • Confusing root access with sorted access: O(1) access to the minimum does not mean the remaining elements are sorted.

  • Ignoring worst-case hash-table behavior: This comparison does not involve hashing, but Python dict operations are O(1) average and O(n) worst case.

  • Forgetting duplicates and negative priorities: Heaps support duplicate values and negative numbers normally.

  • Empty-heap operations: Reading or removing the root of an empty heap is invalid.

  • Using the wrong structure: Interviewers often ask when a sorted array, heap, balanced tree, or hash map is the better choice. Choose a heap when priorities are processed repeatedly; choose a sorted structure when ordered traversal or range queries dominate.

20

How do heaps differ from red-black trees?

A heap efficiently maintains the smallest or largest element, making it ideal for priority queues. A red-black tree is a balanced binary search tree that maintains keys in sorted order, making it suitable for ordered maps and range queries.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Difference and Structure

  • Binary heap: A complete binary tree stored in an array. The root is at index 0; the children of index i are at 2*i + 1 and 2*i + 2; the parent is at (i - 1) // 2. In a min-heap, each parent is no greater than its children; in a max-heap, each parent is no smaller than its children.

  • Red-black tree: A binary search tree with red/black coloring, a black root, black None leaves, no red-red parent-child pair, and equal black-node counts on paths from a node to its descendant leaves. Rotations and recoloring preserve sorted order while keeping the height O(log n).

  • Ordering: A heap has only a partial ordering, so its root is guaranteed to be the extreme element but the remaining elements are not sorted. A red-black tree has a total ordering over its keys, so an in-order traversal produces ascending order.

  • Duplicates: Binary heaps naturally allow duplicate elements. An ordered map normally requires unique keys according to its comparator, although some tree implementations can store additional payloads or comparator-equal keys.

Operation Complexity

Operation Binary heap Red-black tree Reason
Peek at an extreme element O(1) Best O(1); average/worst O(log n) A heap exposes its root; a tree may traverse to an extreme node
Insert Best O(1); average/worst O(log n) O(log n) A heap sifts upward; a tree traverses and rebalances a path
Remove an extreme element Best O(1); average/worst O(log n) O(log n) A heap sifts downward; a tree locates and deletes the node, then fixes its invariants
Locate an arbitrary key O(n) average/worst for a linear scan; O(1) if found at the root Best O(1); average/worst O(log n) A heap may require a scan; a tree follows one branch per comparison
Remove a known element O(log n) after locating it O(log n) after locating it Heap removal sifts from a known index; tree deletion performs fix-up operations
Predecessor/successor No general ordered operation; a scan is O(n) worst case Best O(1); average/worst O(log n) Only the tree maintains a total order
Sorted traversal Not maintained by a heap O(n) The tree visits every node in order
Build from n values heapify: O(n) Typical repeated insertion: O(n log n) Heap construction performs O(n) total sift-down work

Heap insertion and removal are O(log n) because a complete binary heap has height floor(log2 n). Bottom-up heap construction is O(n), not O(n log n), because the total work across the tree’s levels forms a convergent sum bounded by O(n).

Space Complexity

  • Stored elements: Both structures require O(n) space for their elements or nodes.

  • Heap auxiliary space: O(1) for iterative operations or O(log n) for a recursive implementation because the recursion stack is included.

  • Red-black tree auxiliary space: O(log n) for recursive operations or O(1) for iterative updates.

  • Input accounting: Total space including the original input is O(n). Space excluding the original input but including the structure’s own storage is also O(n).

Practical Trade-offs

  • Use a heap for priority queues, task scheduling, event processing, and repeatedly selecting the highest-priority item. Dijkstra’s algorithm uses a heap when edge weights are non-negative.

  • Use a red-black tree for ordered dictionaries, range searches, predecessor/successor queries, and maintaining sorted keys.

  • Heap advantages: Compact array storage, simple implementation, and O(1) access to an extreme element.

  • Heap limitations: No general key lookup, no maintained sorted traversal, and potentially O(n) searching.

  • Red-black tree advantages: O(log n) lookup and modification plus efficient ordered navigation.

  • Red-black tree limitations: More metadata and pointers, greater memory use, and substantially more complex balancing logic.

  • In Python, heapq provides a min-heap; a max-heap can be represented by negating values. Python’s dict is a hash map, not a red-black tree, and its keys are not maintained in sorted order. Python has no built-in tree map; the third-party sortedcontainers package provides SortedDict for ordered maps and SortedList for sorted sequences.

Small Example and Edge Cases

For 42, 17, 93, 8, 55:

  1. Inserting the values into a min-heap makes 8 the root.

  2. Peeking returns 8 in O(1).

  3. Removing 8 replaces it with the last element and sifts downward, making 17 the new root.

  4. Inserting the same values into a red-black tree produces the in-order traversal 8, 17, 42, 55, 93.

  5. Looking up 42 in the tree takes O(log n), while a heap lookup may require a linear scan.

Relevant edge cases are:

  • Empty input: There is no extreme element or key to retrieve.

  • One element: Extreme-element operations and lookups take O(1).

  • Duplicates: Heaps allow them; an ordered map normally uses unique keys.

  • Negative numbers: Both structures handle them normally because ordering does not depend on sign.

  • Already sorted input: Heap construction is still O(n), and sorted input does not change the tree’s standard complexity bounds.

  • Graph-specific cases such as disconnected graphs and cycles do not apply to these structures.

Common Pitfalls

  • Do not call a heap sorted; only its root is guaranteed to be the extreme element.

  • Do not claim arbitrary heap lookup is O(log n).

  • Do not confuse Python’s dict with a red-black tree.

  • Do not assume a red-black tree is perfectly balanced; its coloring rules guarantee only logarithmic height.

  • Common follow-ups include implementing heapify, explaining why it is O(n), implementing a max-heap, and explaining red-black tree insertion and deletion fix-ups.

21

When to use Fibonacci heaps instead of binary heaps?

A Fibonacci heap is most useful when an application performs many decrease-key operations and relatively few delete-min operations. A binary heap is usually the better practical choice because it is simpler, has lower constants, and performs well across general workloads.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How They Work

  • Binary heap: Stores elements in a complete binary tree represented by an array. For an element at index i, its children are at 2i + 1 and 2i + 2, and its parent is at (i - 1) // 2. The heap invariant keeps the minimum element at index 0.

  • Fibonacci heap: Consists of a collection of heap-ordered trees stored through linked lists and pointers. Insertion and melding are cheap, while extracting the minimum consolidates trees of equal degree.

  • Decrease-key: Binary heaps usually repair the heap by moving an element toward the root. Fibonacci heaps detach a changed node, cut it from its parent, and then perform cascading cuts. This is why its amortized cost is much lower.

Complexity Comparison

Operation Binary heap Fibonacci heap
Insert O(log n) worst case O(1) amortized
Find minimum O(1) worst case O(1) worst case
Extract minimum O(log n) worst case O(log n) amortized; a single operation can take O(n)
Delete an arbitrary element O(log n) worst case O(log n) amortized; a single operation can take O(n)
Decrease-key O(log n) worst case O(1) amortized; a single call can cost more because of cascading cuts
Meld two heaps O(n) (concatenate and heapify) O(1)
Space O(n) for the heap; O(1) additional working space O(n) for nodes and links; O(1) additional working space

The input itself is not counted separately from the heap storage. These are deterministic data structures, so there is no separate average-case complexity for their normal operations; “amortized” means the average cost over a sequence of operations.

When Fibonacci Heaps Make Sense

  • Frequent priority reductions: Applications such as graph algorithms repeatedly lower a vertex’s tentative distance.

  • Dijkstra’s algorithm: A classic Fibonacci-heap implementation uses decrease-key and runs in O(E + V log V), compared with O((V + E) log V) for a binary-heap implementation.

  • Meld-heavy workloads: Combining heaps takes O(1) with a Fibonacci heap.

  • Insert-heavy workloads: Insertion takes O(1) amortized rather than O(log n).

The theoretical advantage matters when priority updates dominate the workload and the implementation provides an efficient decrease-key operation.

Why Binary Heaps Are Usually Preferred

  • Simplicity: Binary heaps have straightforward array-based implementations.

  • Lower constants: Cache-friendly array access usually makes binary heaps faster in practice.

  • Predictable worst-case behavior: Most important operations are O(log n) rather than amortized.

  • Better library support: Python’s standard-library heapq implements a binary min-heap, while no Fibonacci heap is included.

  • Memory efficiency: Binary heaps usually store one value per array slot; Fibonacci heaps require additional child, parent, and sibling links.

For most production systems, a binary heap, pairing heap, or d-ary heap is preferable even when a Fibonacci heap has better asymptotic complexity.

Interview Tips

  • Do not claim that every Fibonacci-heap operation is O(1); extract-min and deletion remain O(log n) amortized.

  • Distinguish amortized performance from worst-case performance: a sequence may cost O(1) amortized per decrease-key even though an individual update can trigger a long chain of cascading cuts.

  • Mention that Python’s heapq does not expose decrease-key; applications commonly push updated (priority, item) tuples and skip obsolete entries.

  • Expect follow-up questions about why heap construction is O(n), how cascading cuts preserve the heap invariant, and why Fibonacci heaps are rarely selected in real systems.

22

When should a Binomial Heap be used?

A binomial heap is useful when an application needs a meldable min-priority queue, especially when several priority queues are combined frequently. An indexed binomial heap can also support efficient priority updates through decrease-key, although it remains more complex than a conventional binary heap.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Best-Fit Situations

A binomial heap is a good choice when:

  • Several priority queues must be merged: For example, a distributed scheduler can combine the waiting queues of multiple workers without copying every element.

  • The workload mixes frequent insertions and removals: A min-priority queue naturally supports repeatedly removing the smallest-priority task.

  • Priorities can be updated: An indexed binomial heap supports decrease-key, which is useful in algorithms such as Dijkstra’s shortest-path algorithm.

  • The implementation needs guaranteed logarithmic operations: Unlike some Fibonacci-heap operations, binomial-heap operations have straightforward worst-case logarithmic bounds.

  • Partitioned or batched processing is involved: Independent collections of pending tasks can be maintained separately and then melded into one queue; concurrent access would still require synchronization.

It is usually unnecessary when there is only one queue, no merging, and no priority updates. A simpler binary heap is usually preferable in that case.

Internal Model

A binomial heap is a forest of binomial trees stored as a linked list of roots:

  • A binomial tree B_k contains exactly 2^k nodes and has height k.

  • Every node of degree d has exactly one child of each degree from 0 through d - 1.

  • Each tree obeys the min-heap property: a parent’s key is no greater than its children’s keys.

  • The forest contains at most one root of each degree.

The primary operations work as follows:

  • Insert: Add a one-node tree and meld it with the existing forest.

  • Meld: Combine root lists by degree, repeatedly joining two trees of equal degree.

  • Find minimum: Return the root referenced by the heap’s minimum pointer.

  • Delete minimum: Remove that root, promote its children into the forest, and meld the resulting forests.

  • Decrease-key: In an indexed implementation, move a changed node upward until the heap-order property is restored.

Small Merge Example

Suppose two queues contain priorities {2, 7} and {3, 5}:

  1. Each queue is represented by a B1 tree: 2 → 7 and 3 → 5.

  2. Melding the queues joins the two B1 trees into one B2 tree rooted at 2.

  3. In the new tree, 2 has children 3 and 7, and 3 retains 5 as its child. No B1 tree remains.

  4. The merged heap contains priorities {2, 3, 5, 7}, and its minimum is 2.

Complexity

For n elements, these bounds are deterministic; best, average, and worst cases have the same asymptotic values for the standard operations.

Operation Best Average Worst Reason
Find minimum O(1) O(1) O(1) Uses the minimum pointer
Insert O(log n) O(log n) O(log n) Melds a singleton tree
Meld O(log n) O(log n) O(log n) Combines root lists by degree
Delete minimum O(log n) O(log n) O(log n) Promotes children and melds forests
Decrease-key, indexed variant O(log n) O(log n) O(log n) A node moves toward the root

Total space is O(n), counting the n stored elements and tree links. The root list and any recursive traversal stack use at most O(log n) additional space. The input itself is not counted separately; an additional input copy would add another O(n) space.

Comparison With Other Heaps

Structure Merge Decrease-key Best fit
Binary heap O(n) O(log n) One queue, top-K selection, simpler implementation
Binomial heap O(log n) O(log n) with an indexed variant Frequent melds with guaranteed logarithmic operations
Fibonacci heap O(1) amortized O(1) amortized Very frequent decreases and melds, despite greater complexity

Python’s standard-library heapq implements a binary min-heap, not a binomial heap. Building a binary heap with heapq.heapify is O(n), because the total sift-down work is bounded by a geometric series rather than O(n log n).

Common Pitfalls

  • Do not confuse a binomial heap with a binomial tree or a B-tree.

  • Handle an empty heap explicitly: finding or deleting its minimum is undefined.

  • One-element heaps are valid, and duplicate or negative priorities are allowed.

  • Use a counter as a tie-breaker when priority payloads are not mutually comparable.

  • Input order does not affect correctness; sorted and unsorted input are both accepted.

  • If the heap drives graph processing, use a separate visited set for disconnected graphs and cycles.

23

When should you use a Min-Heap instead of a Max-Heap?

A Min-Heap keeps the smallest element at its root, while a Max-Heap keeps the largest element at the root. Both are useful priority queues, but they support different ordering requirements and use cases.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Behavior

In a binary heap, the root has the highest priority according to the heap’s ordering. The rest of the elements are only partially ordered: every parent precedes its children in the required direction, but sibling subtrees are not globally sorted.

  • Min-Heap: The parent is less than or equal to its children, so the root is the minimum element.

  • Max-Heap: The parent is greater than or equal to its children, so the root is the maximum element.

  • Common use: Implementing priority queues, where the next element to process has the highest priority.

A heap is preferable to a fully sorted list when you need efficient insertion, removal, and priority access without maintaining total order.

Use Cases

Use case Min-Heap Max-Heap
Priority queue Process the item with the smallest key first Process the item with the largest key first
Task scheduling Earliest deadline or lowest cost first Highest severity or value first
Dijkstra’s algorithm Selects the smallest tentative distance Not applicable in standard form
Top K largest elements Keep a size-K min-heap; its root is the smallest of the K largest Heapify all values and pop K times
Kth-largest element The root of the size-K min-heap is the answer Pop K times from a max-heap of all values
Running maximum Not suitable Stores the current maximum at the root
Merging sorted sequences Merge K sorted lists from their smallest fronts Can merge from largest fronts when descending order is required
Huffman coding Selects the least frequent nodes first Not the standard choice

For example, an operating-system scheduler may use a Min-Heap to run the task with the smallest deadline first. A system processing the most severe incidents first would use a Max-Heap with severity as the priority.

Python Implementation Choice

Python’s heapq module implements a Min-Heap:

  • heapq.heappush(heap, value): Inserts an element in O(log n) time.

  • heapq.heappop(heap): Removes the minimum element in O(log n) time.

  • heapq.heapify(heap): Builds a heap in O(n) time.

  • heapq.nsmallest(k, values) and heapq.nlargest(k, values): Find the smallest or largest k elements.

To implement a Max-Heap, negate numeric values before inserting them and negate them again when reading the root. For non-comparable items, store tuples such as (-priority, item). If priorities can tie, add a monotonically increasing counter as a tie-breaker so Python never compares the items themselves.

Complexity

Operation Min-Heap Max-Heap Reason
Peek at root O(1) O(1) The root is stored at a known index
Insert O(log n) O(log n) Restores the heap property along one path
Remove root O(log n) O(log n) Replaces the root and sifts an element downward
Build heap O(n) O(n) Sift-down work decreases with tree depth
Find minimum O(1) Not directly applicable The minimum is not guaranteed to be at the root
Find maximum Not directly applicable O(1) The maximum is guaranteed to be at the root

These bounds are the same for best, average, and worst cases for the standard array-based binary heap. The O(n) heap construction is not O(n log n) because most elements are near the bottom and require little or no sifting.

For a heap containing n elements:

  • Total space: O(n), including the heap array.

  • Auxiliary space: O(1) for core heap operations because they are iterative.

  • Input storage: If the heap is built from an existing list, the list itself occupies O(n) space.

Common Pitfalls

  • Assuming a heap is fully sorted: Only the root is globally extreme; the remaining elements are partially ordered.

  • Using the wrong Python heap type: heapq is a Min-Heap, not a Max-Heap.

  • Negating objects incorrectly: Negation works for numeric values but not arbitrary objects; use (-priority, counter, item) for a Max-Heap.

  • Forgetting tie-breakers: Equal-priority tuples may attempt to compare non-comparable items.

  • Using a heap for range queries: A heap is efficient for priority access, but it does not efficiently answer “how many elements are below a threshold?”

  • Confusing the heap array with sorted order: The list behind heapq is not sorted, although repeated heapq.heappop calls return elements in ascending order.

24

Find the 100 largest values in a billion-element array

Use a fixed-size min-heap containing the 100 largest values seen so far. Its root is the smallest retained value, so each new value can be checked and potentially replace the root in O(log 100) time without storing or sorting the entire input.

Read full answer

Applies toPython 3.12

Approach

For a target count k = 100:

  1. Read the first k values and place them in a list.

  2. Call heapq.heapify to turn the list into a min-heap in O(k) time.

  3. For every remaining value:

  4. If it is no larger than the heap root, ignore it.

  5. Otherwise, replace the root with it using heapq.heapreplace.

  6. Sort the final heap in descending order if ordered output is required.

The heap always contains the largest k values encountered so far. Because heapq implements a min-heap, the smallest retained value is conveniently available at index 0.

heapq.heapify is O(k), not O(k log k), because it performs a bottom-up heap construction. The total work across the tree’s levels forms a geometric series, so it is linear in the number of elements.

Complexity

Let n be the number of input values and k = 100.

  • Best case: O(n + k log k) — the scan is linear, no heap replacements are needed, and sorting the final output costs O(k log k).

  • Average case: O(n log k) upper bound — many values may qualify for replacement, although a random input produces fewer replacements than the worst case.

  • Worst case: O(n log k) — every value after the first k can replace the heap root.

  • Extra space: O(k) — the heap and returned result each contain at most k values. The input itself is not counted.

For fixed k = 100, log k is constant, so the overall scan is linear in n with a relatively small constant.

Approach Comparison

Approach Time Extra space When to use
Sort the entire input O(n log n) Up to O(n) Small inputs or when the complete sorted order is needed
Fixed-size min-heap O(n log k) worst case O(k) Streaming input, predictable memory, no input mutation
Quickselect-style partitioning O(n) average, O(n²) worst O(k) result plus partition storage Random-access mutable array where average-case speed matters

Quickselect is faster on average for an in-memory random-access array, but it usually mutates the array and has a worse worst case. The heap approach is often preferable when processing a billion values sequentially or from a stream.

Example Walkthrough

For values = [5, 1, 9, 9, 3, 12, 2] and k = 3:

  1. Collect the first three values: [5, 1, 9].

  2. Heapify them: [1, 5, 9].

  3. Read 9: it exceeds the root 1, so replace it with 9, producing [5, 9, 9].

  4. Read 3: it does not exceed the root 5, so ignore it.

  5. Read 12: it exceeds the root 5, so replace it, producing [9, 12, 9].

  6. Read 2: ignore it.

  7. Sort the final heap to obtain [12, 9, 9].

Code Example

from collections.abc import Iterable
import heapq


def find_largest(values: Iterable[int], count: int = 100) -> list[int]:
    """Return up to count largest values in descending order."""
    if count <= 0:
        return []

    largest: list[int] = []

    for value in values:
        if len(largest) < count:
            largest.append(value)

            if len(largest) == count:
                heapq.heapify(largest)

        elif value > largest[0]:
            # Remove the smallest retained value and insert the new one.
            heapq.heapreplace(largest, value)

    return sorted(largest, reverse=True)


print(find_largest([5, 1, 9, 9, 3, 12, 2], count=3))
# Expected output: [12, 9, 9]

Common Pitfalls

  • Using a max-heap incorrectly: heapq is a min-heap. Keep the largest k values with its smallest element at the root.

  • heapreplace vs heappushpop: heapq.heapreplace pops the root before pushing, so it is correct only after checking value > largest[0], as the code does. heapq.heappushpop pushes first and needs no check.

  • Ignoring ties: Duplicate values count separately. A new value equal to the root may be skipped without changing the resulting multiset of values.

  • Materializing one billion Python integers: This can consume enormous memory. Prefer a generator, compact numeric array, or streamed input.

  • Forgetting edge cases: The function handles empty input, fewer than count values, one element, duplicates, negative numbers, and already sorted input.

  • Confusing output order: The heap itself is unordered; the final sorted call provides descending order.

25

How do you implement Decrease-Key in a binary heap?

Decrease-Key in a binary heap replaces an element’s key with a smaller value and restores the heap property by moving the element upward toward the root. In a min-heap, the new key must be less than or equal to the old key.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A binary heap is a complete binary tree stored in an array:

  • The parent of index i is (i - 1) // 2.

  • The left child of index i is 2 * i + 1.

  • The right child of index i is 2 * i + 2.

  • The root is index 0.

For a min-heap, every parent must be less than or equal to its children. After decreasing the key at index:

  1. Replace the key at index with new_key.

  2. Compare it with its parent.

  3. If the parent is larger, swap the two elements.

  4. Repeat until the parent is no larger than the current element or the root is reached.

No downward movement is needed because only a smaller value is introduced.

Complexity

Operation Best case Average case Worst case Reason
Decrease-Key O(1) O(log n) O(log n) The element may move through every level of the heap
  • Time: O(log n) worst case because the heap has height floor(log₂ n).

  • Auxiliary space: O(1), since the operation modifies the heap in place.

  • Input space: The existing heap uses O(n) space; this is not additional auxiliary space.

  • Recursion stack: O(1), because the implementation is iterative.

Code Example

def decrease_key(heap: list[int], index: int, new_key: int) -> None:
    """Decrease the key at an index in a min-heap and restore heap order."""
    if not heap:
        raise IndexError("cannot decrease a key in an empty heap")

    if index < 0 or index >= len(heap):
        raise IndexError("heap index is out of range")

    if new_key > heap[index]:
        raise ValueError("new_key must not be greater than the current key")

    heap[index] = new_key

    # Restore the min-heap property by moving the element upward.
    while index > 0:
        parent = (index - 1) // 2

        if heap[parent] <= heap[index]:
            break

        heap[parent], heap[index] = heap[index], heap[parent]
        index = parent


heap = [1, 5, 3, 7, 6, 8]
decrease_key(heap, 4, 2)
print(heap)  # Expected output: [1, 2, 3, 7, 5, 8]

Example Walkthrough

Starting with:

[1, 5, 3, 7, 6, 8]

The key at index 4 is decreased from 6 to 2:

[1, 5, 3, 7, 2, 8]

The parent at index (4 - 1) // 2 = 1 contains 5, so the values are swapped:

[1, 2, 3, 7, 5, 8]

The new parent contains 1, which is already less than or equal to 2, so the operation stops.

Common Pitfalls

  • Using the wrong comparison: A min-heap moves smaller values upward; a max-heap uses the opposite comparison.

  • Allowing an increase: Standard Decrease-Key rejects a new value greater than the current value. Increasing a value would require a downward sift.

  • Confusing parent and child formulas: The parent is (i - 1) // 2, not i // 2.

  • Losing track of the element: If the caller needs to update the same element repeatedly, maintain a stable index or object handle and update it whenever the element is swapped.

  • Ignoring edge cases: Empty heaps and invalid indices should raise an error. One-element heaps, duplicate values, and negative values work with the same logic.

  • Assuming Python’s heapq supports this directly: heapq provides heap operations but does not expose a standard Decrease-Key operation. Implement the operation over the internal list when direct index-based access is required.

Interview Tips

Interviewers may ask about the difference between Decrease-Key and Delete, how to implement the operation in a max-heap, or how to support locating an element by value. For repeated updates, maintain an auxiliary mapping from element identity to its current heap index and keep that mapping synchronized during swaps.

26

Find the kth smallest element in a min-heap without modifying it

A bounded auxiliary max-heap keeps the k smallest values seen so far without changing the original min-heap. Python’s heapq is a min-heap, so negating values lets the auxiliary heap behave like a max-heap.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

The root of the original min-heap is the smallest element, but a min-heap does not store its remaining elements in sorted order. To find the kth smallest element:

  1. Take the first k elements and store their negations in an auxiliary heap.

  2. heapify the auxiliary heap in O(k) time.

  3. Scan the remaining original elements.

  4. If a value is smaller than the largest value currently retained, replace that largest value.

  5. The largest value in the auxiliary heap is the kth smallest value overall.

The original heap is only indexed and read; it is never modified.

Complexity

Let n be the number of elements and k the requested rank.

Approach Best case Average case Worst case Extra space
Sort a copy O(n log n) O(n log n) O(n log n) O(n)
Bounded auxiliary max-heap O(n) O(n log(k + 1)) O(n log(k + 1)) O(k)

For the implemented approach, the more precise bound is O(k + (n - k) log(k + 1)): heap construction costs O(k), and each later replacement costs O(log k). The auxiliary space is O(k), excluding the input heap. Including the input, total space is O(n + k) = O(n). The recursion stack is O(1) because the implementation is iterative.

heapify is linear rather than O(k log k) because it performs bottom-up sift-down operations whose total cost is proportional to the number of elements.

Code Example

from collections.abc import Sequence
from heapq import heapify, heapreplace


def kth_smallest_in_min_heap(heap: Sequence[int], k: int) -> int:
    """Return the kth smallest value without modifying the original min-heap."""
    if not heap:
        raise ValueError("heap must not be empty")
    if not 1 <= k <= len(heap):
        raise ValueError("k must be between 1 and len(heap)")

    # Negated values make heapq behave as a bounded max-heap.
    candidates = [-heap[index] for index in range(k)]
    heapify(candidates)

    for index in range(k, len(heap)):
        value = heap[index]
        largest_retained = -candidates[0]

        if value < largest_retained:
            heapreplace(candidates, -value)

    return -candidates[0]


heap = [2, 3, 1, 7, 5]
print(kth_smallest_in_min_heap(heap, 3))  # 3

Walkthrough

For heap = [2, 3, 1, 7, 5] and k = 3:

  1. The initial retained values are [2, 3, 1], whose largest value is 3.

  2. The next value, 7, is larger than 3, so it is ignored.

  3. The next value, 5, is also larger than 3, so it is ignored.

  4. The retained values are therefore the three smallest values: 1, 2, and 3.

  5. The auxiliary heap returns 3, the third smallest element.

Common Pitfalls

  • Empty heap: The function raises ValueError; there is no valid rank.

  • Invalid k: Require 1 <= k <= len(heap).

  • Duplicates: Each occurrence counts separately, as in a standard sorted collection.

  • Negative values: Negation still works because the auxiliary heap only compares numeric values.

  • One element or already sorted input: The function returns the only element or the element at the requested sorted position correctly.

  • Using pop(0) or insert(0, value): Avoid these operations in loops because they require O(n) shifting.

  • Assuming heap order is sorted order: A min-heap only guarantees that each parent is no greater than its children.

  • Disconnected graphs and cycles are not applicable to this heap operation.

27

How do you implement deletion of arbitrary elements in a heap?

An indexed heap supports deletion of any element by locating its position in the underlying array, replacing it with the last element, and then restoring the heap property. A hash map tracks the current index of each value, so the operation remains efficient despite array reordering.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A binary heap is stored as a complete binary tree in an array:

  • Left child of index i: 2 * i + 1

  • Right child of index i: 2 * i + 2

  • Parent of index i: (i - 1) // 2

The implementation below stores:

  • _values: the heap’s array representation.

  • _positions: a map from each value to the set of indices containing it.

Deleting an element at index index works as follows:

  1. Save the element being removed.

  2. Remove the last element from the array.

  3. Place that last element at the deleted position.

  4. Compare it with its parent:

  5. If it is smaller than its parent, sift it up.

  6. Otherwise, sift it down.

  7. Update the position map during every swap.

A set is used for the position map so duplicate values are handled correctly. delete_value removes one occurrence of a value.

Complexity

Operation Best case Average case Worst case Space
delete_at(index) O(1) O(log n) O(log n) O(1) auxiliary
delete_value(value) O(1) O(log n) O(n log n) with adversarial hash collisions O(1) auxiliary
  • delete_at performs at most O(log n) sift steps because the heap height is O(log n).

  • delete_value requires an O(1) average-time hash-map lookup, followed by an O(log n) heap repair.

  • Python dictionaries can take O(n) per lookup or update in the presence of severe hash collisions, so the conservative worst case is O(n log n).

  • Total storage is O(n) for the heap and position map.

  • The input collection itself is not counted. The constructor copies the supplied values into the heap, requiring O(n) additional storage.

  • All operations are iterative, so the recursion stack uses O(1) space.

Code Example

from collections.abc import Iterable
from typing import Generic, TypeVar

T = TypeVar("T")


class IndexedMinHeap(Generic[T]):
    """A min-heap supporting deletion by index or value."""

    def __init__(self, values: Iterable[T]) -> None:
        self._values: list[T] = list(values)
        self._positions: dict[T, set[int]] = {}

        for index, value in enumerate(self._values):
            self._positions.setdefault(value, set()).add(index)

        # Build the heap from the bottom up.
        for index in range(len(self._values) // 2 - 1, -1, -1):
            self._sift_down(index)

    def __len__(self) -> int:
        return len(self._values)

    def peek(self) -> T:
        """Return the smallest element without removing it."""
        if not self._values:
            raise IndexError("peek from an empty heap")
        return self._values[0]

    @property
    def values(self) -> list[T]:
        """Return a copy of the heap's current array representation."""
        return self._values.copy()

    def delete_at(self, index: int) -> T:
        """Delete and return the element at the specified array index."""
        if not self._values:
            raise IndexError("delete from an empty heap")
        if index < 0 or index >= len(self._values):
            raise IndexError("heap index out of range")

        removed = self._values[index]
        last_index = len(self._values) - 1

        if index == last_index:
            self._values.pop()
            self._remove_position(removed, last_index)
            return removed

        last_value = self._values.pop()
        # Remove the positions of the removed element and the last element
        self._remove_position(removed, index)
        self._remove_position(last_value, last_index)

        # Place the last element at the deleted position
        self._values[index] = last_value
        self._positions.setdefault(last_value, set()).add(index)

        # Restore heap property
        parent = (index - 1) // 2
        if index > 0 and self._values[index] < self._values[parent]:
            self._sift_up(index)
        else:
            self._sift_down(index)

        return removed

    def delete_value(self, value: T) -> T:
        """Delete and return one occurrence of value."""
        indices = self._positions.get(value)
        if indices is None:
            raise ValueError(f"value not found in heap: {value!r}")
        index = next(iter(indices))
        return self.delete_at(index)

    def _remove_position(self, value: T, index: int) -> None:
        indices = self._positions[value]
        indices.remove(index)
        if not indices:
            del self._positions[value]

    def _swap(self, left: int, right: int) -> None:
        left_value = self._values[left]
        right_value = self._values[right]

        if left_value == right_value:
            return

        self._values[left], self._values[right] = right_value, left_value

        # Update positions: left_value moves to right, right_value moves to left
        self._positions[left_value].remove(left)
        self._positions[left_value].add(right)
        self._positions[right_value].remove(right)
        self._positions[right_value].add(left)

    def _sift_up(self, index: int) -> None:
        while index > 0:
            parent = (index - 1) // 2
            if self._values[index] >= self._values[parent]:
                break
            self._swap(index, parent)
            index = parent

    def _sift_down(self, index: int) -> None:
        size = len(self._values)
        while True:
            left = 2 * index + 1
            if left >= size:
                break
            right = left + 1
            smaller_child = left
            if right < size and self._values[right] < self._values[left]:
                smaller_child = right
            if self._values[index] <= self._values[smaller_child]:
                break
            self._swap(index, smaller_child)
            index = smaller_child


# Example usage
heap = IndexedMinHeap([1, 3, 2, 7, 5])
heap.delete_value(3)
print(heap.values)  # [1, 5, 2, 7]

Example Walkthrough

Starting heap array after heapify (the input [1, 3, 2, 7, 5] is already a valid min-heap):

[1, 3, 2, 7, 5]

Deleting 3:

  1. 3 is at index 1.

  2. Replace it with the last element, 5: [1, 5, 2, 7].

  3. 5 is not smaller than its parent (1), so sift down.

  4. 5’s only child is 7 at index 3; 5 <= 7, so the heap is valid.

The final heap is:

[1, 5, 2, 7]

Common Pitfalls

  • Using heapq for arbitrary deletion: heapq has no efficient arbitrary-delete operation. Removing an item from its list is O(n).

  • Forgetting index updates: Every swap changes the indices of two values, so the position map must be updated.

  • Ignoring duplicates: A single value can occur at multiple indices. The implementation uses a set of indices and removes only one occurrence.

  • Mutating the input: The constructor copies the iterable, so the caller’s collection is not modified.

  • Using recursive operations: The example is iterative and avoids Python’s recursion-depth limit.

  • Assuming arbitrary elements are usable as keys: Values used with delete_value must be hashable and comparable.

28

What is the difference between a Map and a Heap?

A Map is a data structure that stores key-value pairs, allowing fast retrieval based on a unique key, while a Heap is a specialized tree-based structure that maintains a specific order based on priority, typically used for accessing the smallest or largest element efficiently.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

What is a Map?

A Map (also called a dictionary, associative array, or symbol table) stores data as key-value pairs. The core contract is that every key is unique, and you can look up, insert, or delete a value in time proportional to the key’s hash or its position in a tree.

  • Hash Map: Uses a hash function to compute an index into an array of buckets. This is what Python’s dict implements.

  • Tree Map: Uses a balanced binary search tree (BST) to keep keys sorted. Python has no built-in tree map, so you must use the bisect module on a sorted list or a third-party sorted container.

Complexity: - Time: Search, insert, and delete are O(1) on average for a hash map because the hash function points directly to the bucket. The worst case is O(n) if all keys collide into the same bucket. For a tree map, all operations are O(log n) because the tree stays balanced. - Space: O(n) to store the keys and values, where n is the number of entries. The input itself is counted as part of the storage.

What is a Heap?

A heap is a complete binary tree stored in an array. Because the tree is complete, it can be represented compactly without pointers. The children of index i are at 2i+1 and 2i+2, and the parent is at (i-1)//2.

  • Min-Heap: The parent is always smaller than or equal to its children. The root is the minimum element. Python’s heapq module implements a min-heap.

  • Max-Heap: The parent is always greater than or equal to its children. The root is the maximum element. You can simulate this in Python by pushing negated values or tuples like (-priority, item).

Complexity: - Time: Push and pop are O(log n) because an element must travel from the leaf to the root or vice versa, moving through the tree’s height. Peek is O(1) because the root is at index 0. - Heapify: Building a heap from an unsorted list is O(n), not O(n log n). This is because most nodes are near the bottom of the tree and require little or no movement; the work decreases exponentially as you move up the levels. - Space: O(n) to store the elements in the underlying array.

Key Differences

The fundamental difference is the access pattern: a Map is optimized for lookup by key, while a Heap is optimized for access by priority.

Feature Map Heap
Primary Use Storing and retrieving values by unique key Managing elements by priority (min or max)
Ordering Unordered (hash) or Sorted (tree) Partial order: parent vs. child only
Search O(1) average (hash) or O(log n) (tree) O(n); you cannot search efficiently
Insert O(1) average (hash) or O(log n) (tree) O(log n)
Delete O(1) average (hash) or O(log n) (tree) O(log n) (delete root)
Access By key Root (min or max)

When to Use Which

  • Use a Map when you need to check membership, count frequencies, or retrieve data by an identifier. For example, use collections.Counter for frequency counting or dict for caching results.

  • Use a Heap when you need the top K elements, the Kth largest value, or to merge K sorted lists. For example, use heapq.nlargest to find the top scores in a game.

  • Use a Heap for task scheduling where the next task depends on urgency rather than arrival order.

  • Use a Map when you need to maintain a collection of unique items without regard to their relative order.

Common Pitfalls

  • Confusing heap order with sorted order: A heap is not sorted. Only the root is the min or max. Do not assume the array representation is sorted.

  • Assuming heap search is fast: You cannot search a heap for an arbitrary value faster than O(n) because the structure does not guarantee ordering between siblings.

  • Ignoring collisions in hash maps: In a bad case, a hash map degrades to O(n) performance. Interviewers often ask how to handle this (e.g., chaining or open addressing).

  • Forgetting tie-breakers in heaps: When using heapq with tuples, if the priorities are equal, Python compares the next item. Ensure items are comparable or add a counter to avoid TypeError.

  • Misusing list.pop(0): Removing the first element of a list is O(n). Use collections.deque for queues or heapq for priority queues.

  • Follow-up questions: Interviewers often ask how to implement a heap using an array, or how to implement a Map using a hash function. Be ready to explain the indexing math.

29

How does a hash map work internally in Python?

A hash map stores key-value pairs and uses a hash function to determine where each pair belongs in an internal table. CPython’s dict uses open addressing with probing, providing expected constant-time lookup, insertion, and deletion while handling hash collisions.

Read full answer

Applies toPython 3.12 (CPython)

How It Works

  1. Hash the key: The key must be hashable, such as an int, str, or a tuple or frozenset whose elements are all hashable. Python’s hash() returns an integer hash value.

  2. Select a bucket: The hash value is transformed into an index in the underlying table.

  3. Resolve collisions: Different keys can hash to the same index. A hash map finds the matching stored key using identity or equality.

  4. Store the pair: The key and its associated value are placed in the selected entry.

  5. Resize when necessary: When the table becomes too crowded, the map allocates a larger table and rehashes or reinserts its entries.

A hash map does not generally keep keys sorted. Python’s dict preserves insertion order, but it is not a sorted map. An ordered or tree-based map maintains sorted keys and typically provides O(log n) lookup, which is useful for range queries or sorted iteration.

Internal Python Details

CPython’s dict uses open addressing rather than linked-list buckets. It maintains compact index and entry storage and probes subsequent positions when the preferred position is occupied. Deleted entries use a dummy marker so that later insertions can continue probing correctly.

The implementation below is an educational hash map using separate chaining, where each bucket contains a list of key-value pairs. It demonstrates core operations but does not reproduce CPython’s probing mechanism.

Edge cases handled by the example include an empty map, one entry, duplicate keys updating the existing value, and negative integer keys. Inserting keys in sorted order does not change hash placement; the example does not provide sorted iteration.

Complexity

Operation Best case Average case Worst case Reason
Insert or update O(1) O(1) amortized O(n) Resizing is occasional, while many colliding keys can lengthen a chain.
Lookup O(1) O(1) O(n) Every key may have collided into one bucket.
Delete O(1) O(1) O(n) Searching or removing from a long chain can take linear time.
Resize O(n) O(n) O(n) Every existing entry must be reinserted.

The map stores O(n) space for n entries. Basic non-resizing operations use O(1) auxiliary space, excluding the map’s storage; resizing temporarily uses O(n) additional space. The input is not separately counted, and there is no recursion stack.

Code Example

from collections.abc import Hashable


class HashMap:
    """A small educational hash map using separate chaining."""

    def __init__(self, capacity: int = 8) -> None:
        if capacity < 1:
            raise ValueError("capacity must be positive")

        self._buckets: list[list[tuple[Hashable, object]]] = [
            [] for _ in range(capacity)
        ]
        self._size = 0

    def _index(self, key: Hashable) -> int:
        return hash(key) % len(self._buckets)

    def _insert(self, key: Hashable, value: object) -> None:
        bucket = self._buckets[self._index(key)]
        bucket.append((key, value))
        self._size += 1

    def set(self, key: Hashable, value: object) -> None:
        bucket = self._buckets[self._index(key)]

        # Update the value if the key already exists.
        for position, (existing_key, _) in enumerate(bucket):
            if existing_key == key:
                bucket[position] = (key, value)
                return

        self._insert(key, value)

        # Keep the load factor below approximately 0.75.
        if self._size > len(self._buckets) * 0.75:
            self._resize()

    def get(self, key: Hashable, default: object | None = None) -> object | None:
        bucket = self._buckets[self._index(key)]

        for existing_key, value in bucket:
            if existing_key == key:
                return value

        return default

    def contains(self, key: Hashable) -> bool:
        bucket = self._buckets[self._index(key)]
        return any(existing_key == key for existing_key, _ in bucket)

    def delete(self, key: Hashable) -> bool:
        bucket = self._buckets[self._index(key)]

        for position, (existing_key, _) in enumerate(bucket):
            if existing_key == key:
                bucket.pop(position)
                self._size -= 1
                return True

        return False

    def _resize(self) -> None:
        old_buckets = self._buckets
        self._buckets = [[] for _ in range(len(old_buckets) * 2)]
        self._size = 0

        for bucket in old_buckets:
            for key, value in bucket:
                self._insert(key, value)


example = HashMap()
example.set("a", 1)
example.set("b", 2)
example.set("a", 10)

print(example.get("a"))       # 10
print(example.contains("a"))  # True
print(example.delete("a"))   # True
print(example.get("a"))       # None

For a small trace, set("a", 1) hashes "a" and selects a bucket. set("b", 2) selects another bucket or the same one if a collision occurs. When set("a", 10) runs, the original bucket is selected and the existing key is found with ==, so its value is updated rather than duplicated. delete("a") then removes that pair from the chain.

Interview Tips

  • Do not assume sorted order: A hash map supports fast lookup, not range queries.

  • Avoid mutable keys: Changing a key after insertion can make it unreachable because its hash may change.

  • Handle None values explicitly: Use contains or a sentinel when None is a valid stored value.

  • Discuss collision handling: Mention probing, chaining, load factor, resizing, and deletion tombstones.

  • Use the built-in dict in production: CPython’s implementation is optimized and substantially more robust than this educational version.

30

What collision resolution strategies are used in hash maps?

A collision occurs when two keys produce the same hash-table index. Collision resolution determines how a map stores and retrieves colliding keys, commonly through separate chaining or open addressing.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Strategies

  • Separate chaining: Each bucket stores all entries whose keys hash to that bucket. Buckets commonly use linked lists, dynamic arrays, or balanced search trees. Chaining tolerates high load factors well, but long chains increase lookup time.

  • Linear probing: Open addressing searches consecutive positions using P(i) = (h(key) + i) mod m. It is simple and cache-friendly, but primary clustering can create long groups of occupied slots.

  • Quadratic probing: Searches using a sequence such as P(i) = (h(key) + c₁i² + c₂i) mod m. It reduces primary clustering but can introduce secondary clustering. The table size and coefficients must ensure that probe sequences can reach every slot; otherwise, a table may appear full despite having unused positions.

  • Double hashing: Uses a second hash function: P(i) = (h₁(key) + i × h₂(key)) mod m. This often distributes keys more evenly than linear or quadratic probing. The second step size should be relatively prime to the table size so that the probe sequence can visit every slot.

  • Robin Hood hashing: An open-addressing variant that compares probe distances and swaps entries when a later key has traveled farther. It reduces variance in probe lengths, although deletion requires careful backward shifting or tombstone handling.

Complexity

Here, n is the number of stored entries, m is the table capacity, and α = n/m is the load factor. These bounds assume O(1) key hashing and uniform hashing.

Strategy Best lookup Average lookup Worst lookup Space
Separate chaining with linked lists O(1) Expected O(1 + α) O(n) O(n + m)
Open addressing O(1) Expected O(1) when α is bounded O(n) O(m)
Robin Hood hashing O(1) Expected O(1) when α is bounded O(n) O(m)
  • Chaining costs: A linked-list lookup examines an expected α entries in its bucket and can examine all n entries in the worst case. Storage is O(n + m) because it includes both the entries and bucket headers.

  • Tree buckets: A balanced-tree bucket changes per-bucket search to O(log k), where k is the number of entries in that bucket. Its expected lookup is O(1 + log(1 + α)), and its worst-case lookup is O(log n).

  • Open-addressing costs: A lookup examines occupied probe positions until it finds the key or an unused slot. With bounded load and uniform hashing, the expected number of probes is constant; a worst-case lookup can scan all n entries.

  • Insertion and deletion: Inserting a new key into a linked-list chain can be O(1), while finding an existing key to update is expected O(1 + α). Open-addressing insertion is expected O(1) under bounded load, and geometric resizing makes insertion O(1) amortized on average over a sequence of insertions. A single insertion without resizing or a deletion requiring a long backward shift can take O(n).

  • Python behavior: In CPython 3.12, dict (a compact table) and set both use open addressing rather than separate chaining. Typical operations are best and average O(1), with insertion O(1) amortized on average, but pathological collisions can make an operation O(n). Their storage is O(n), including allocated table capacity. dict preserves insertion order; set iteration order is arbitrary. Neither is sorted by key.

  • Space excludes the input itself. These operations are nonrecursive, so the recursion-stack space is O(1).

Resolution Walkthrough

Suppose "A", "AA", and "AAA" all have home index 0 in a table of size 5.

  1. Separate chaining stores all three entries in bucket 0; one possible linked-list representation is "A" → "AA" → "AAA".

  2. Linear probing places "A" in slot 0, "AA" in slot 1, and "AAA" in slot 2.

  3. A lookup for "AAA" checks its home slot and then follows the applicable probe sequence until it finds the key or reaches an unused slot that proves the key is absent.

Interview Tips

  • Mention the load factor: probing performance deteriorates substantially as the table becomes nearly full.

  • In open addressing, deletion requires a tombstone or backward-shift deletion; simply clearing a slot can break lookup probe sequences.

  • Avoid a fixed table that can permanently fill. Use resizing and rehashing, or use separate chaining.

  • Test empty maps, one entry, duplicate keys, and adversarially chosen keys that produce many collisions.

  • Common follow-up questions cover clustering, tombstone accumulation, hash-flooding attacks, tree buckets, and how CPython’s dict differs from a textbook hash table.

31

How do you implement a hash map with chaining?

A hash map with chaining resolves hash collisions by storing multiple key-value pairs in the same bucket. Each bucket contains a list, so colliding keys are searched within that list rather than replacing one another.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Chaining Works

  • Compute a key’s bucket with hash(key) % bucket_count.

  • Search that bucket for an equal key.

  • If found, update its value.

  • Otherwise, append the new key-value pair to the bucket.

  • Keep the number of entries below a load factor by resizing and rehashing the buckets.

Unlike open addressing, chaining does not require probing other buckets after a collision.

Approach Time per operation Space When to use
Linear scan Best O(1); average and worst O(n) O(n) Very small collections
Separate chaining Best O(1); average O(1), with amortized O(1) insertion; worst O(n) O(n + b) General-purpose hash mapping
Balanced tree map O(log n) in all cases O(n) Sorted iteration, ranges, and ranking

Python has no built-in balanced tree map. A sorted list can use bisect for O(log n) searches, but insertions and deletions are O(n) because elements must shift. sortedcontainers.SortedDict is a third-party option and is not part of the standard library.

Core Operations

  • put(key, value): Updates an existing key or inserts a new key-value pair.

  • get(key, default): Returns the value for a key or a default value when absent.

  • remove(key): Removes the first matching key and reports whether it existed.

  • contains(key): Checks whether a key exists.

  • len(map): Returns the number of stored entries.

Duplicate keys update the existing value instead of creating duplicates. Empty maps, missing keys, one-element maps, negative keys, and hash collisions are handled normally.

Complexity

Let n be the number of entries and b the number of buckets.

Operation Best Average Worst
put O(1) O(1) amortized O(n)
get O(1) O(1) O(n)
remove O(1) O(1) O(n)
contains O(1) O(1) O(n)

The average bounds assume a good hash function and a controlled load factor. A single operation can be O(n) when all keys hash to one bucket or when insertion triggers a resize.

  • Time for resizing: O(n + b), which is O(n) when bucket capacity grows proportionally with the number of entries. Doubling the capacity makes insertion O(1) amortized over a sequence of insertions.

  • Space: O(n + b), including stored entries, the bucket array, and temporary bucket arrays during resizing. A caller-owned input is not counted separately, and the recursion stack is O(1).

Example Walkthrough

With four buckets, integer keys 1 and 5 both map to bucket 1:

  1. put(1, 10) creates bucket 1 containing (1, 10).

  2. put(5, 50) encounters a collision and appends (5, 50) to that bucket.

  3. put(1, 11) finds key 1 and updates its value.

  4. get(1) returns 11.

  5. remove(5) removes only the second entry, leaving one map entry.

Code Example

from collections.abc import Hashable
from typing import Generic, TypeVar

K = TypeVar("K", bound=Hashable)
V = TypeVar("V")


class HashMap(Generic[K, V]):
    """A hash map that resolves collisions using separate chaining."""

    def __init__(self, capacity: int = 8, load_factor: float = 0.75) -> None:
        if capacity < 1:
            raise ValueError("capacity must be at least 1")
        if not 0 < load_factor <= 1:
            raise ValueError("load_factor must be in the range (0, 1]")

        self._load_factor = load_factor
        self._buckets: list[list[tuple[K, V]]] = [
            [] for _ in range(capacity)
        ]
        self._size = 0

    def _bucket_index(self, key: K) -> int:
        # Modulo also normalizes negative hash results to valid indexes.
        return hash(key) % len(self._buckets)

    def put(self, key: K, value: V) -> None:
        bucket = self._buckets[self._bucket_index(key)]

        for index, (stored_key, _) in enumerate(bucket):
            if stored_key == key:
                # Preserve the original key object and do not compare values.
                bucket[index] = (stored_key, value)
                return

        if self._size + 1 > len(self._buckets) * self._load_factor:
            self._resize(len(self._buckets) * 2)
            self._buckets[self._bucket_index(key)].append((key, value))
        else:
            bucket.append((key, value))

        self._size += 1

    def get(self, key: K, default: V | None = None) -> V | None:
        for stored_key, value in self._buckets[self._bucket_index(key)]:
            if stored_key == key:
                return value
        return default

    def remove(self, key: K) -> bool:
        bucket = self._buckets[self._bucket_index(key)]

        for index, (stored_key, _) in enumerate(bucket):
            if stored_key == key:
                bucket.pop(index)
                self._size -= 1
                return True

        return False

    def contains(self, key: K) -> bool:
        return any(
            stored_key == key
            for stored_key, _ in self._buckets[self._bucket_index(key)]
        )

    def _resize(self, new_capacity: int) -> None:
        old_buckets = self._buckets
        self._buckets = [[] for _ in range(new_capacity)]
        self._size = 0

        for bucket in old_buckets:
            for key, value in bucket:
                self._buckets[self._bucket_index(key)].append((key, value))
                self._size += 1

    def __len__(self) -> int:
        return self._size


def demo() -> None:
    """Demonstrate collision handling, updating, and removal."""
    values = HashMap[int, int](capacity=4)

    values.put(1, 10)
    values.put(5, 50)  # Collision: both keys use the same bucket.
    values.put(1, 11)

    print(values.get(1))
    print(values.get(5))
    print(values.remove(5))
    print(len(values))

    # Expected output:
    # 11
    # 50
    # True
    # 1


if __name__ == "__main__":
    demo()

Common Pitfalls

  • Do not assume every operation is O(1): collisions make lookup and insertion O(n) in the worst case.

  • Do not forget resizing cost: a resize is O(n), although doubling capacity gives amortized O(1) insertion.

  • Do not mutate keys after insertion: changing a key’s value can change its hash and make it difficult to locate.

  • Do not confuse duplicates with distinct colliding keys: equality determines whether a key updates an existing entry.

  • Missing values versus stored None: get returns None for both by default; use contains to distinguish them.

32

Tree map vs hash map: how and when to use?

A tree map is an ordered map backed by a balanced binary search tree, keeping keys sorted and supporting logarithmic-time lookups, insertions and deletions. You would use it over a hash map when you need sorted keys, range queries, or ordered iteration, and when worst-case performance guarantees matter more than average-case speed.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Binary search tree: each node stores a key-value pair with left and right children.

  • Ordering: left subtree keys are less than the node’s key; right subtree keys are greater.

  • Balancing: real tree maps use AVL or Red-Black trees to keep height logarithmic.

  • Operations: insert, search, delete, and successor/predecessor run in O(log n) time on a balanced tree.

  • Space: O(n) for n nodes; iterative operations use O(1) auxiliary space, while recursive implementations would use O(h) recursion stack (h = tree height).

Tree Map vs Hash Map

Operation Tree Map Hash Map
Lookup O(log n) O(1) average, O(n) worst
Insert O(log n) O(1) average, O(n) worst
Delete O(log n) O(1) average, O(n) worst
Iteration Sorted order Arbitrary order
Range queries O(log n + k) O(n)
Memory Higher (pointers) Lower (array-based)

When to Use a Tree Map

  • Sorted keys: when you need to iterate keys in order.

  • Range queries: when you need all keys between two values.

  • Order statistics: when you need the k-th smallest key.

  • Worst-case guarantees: when you cannot accept O(n) worst-case lookups.

Common Pitfalls

  • Unbalanced trees: a naive BST can degrade to O(n) for operations.

  • Hash map order: hash maps do not preserve order; use a tree map for sorted iteration.

  • Range queries: range queries are inefficient on hash maps.

  • Memory overhead: tree maps use more memory due to node pointers.

33

What trade-offs does an array-backed map implementation have?

A typical unsorted array-backed map stores key-value entries in an array and finds entries by scanning. This trades the average constant-time operations of a hash map for a simple representation with good sequential locality; sorted array-backed variants can use binary search, but pay linear insertion and removal costs.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

An unsorted array-backed map commonly stores entries as (key, value) tuples:

  • Insert or update: Scan for an existing key; update its value if found, otherwise append a new entry.

  • Lookup: Scan until the matching key is found.

  • Remove: Locate the entry, then delete it, shifting later entries when necessary.

  • Iteration: Visit entries in their underlying array order.

Duplicate keys are not stored twice: updating an existing key replaces its previous value. Unlike a hash map, an array-backed map can use unhashable keys, provided the keys support meaningful equality comparisons.

A sorted array-backed map follows the same basic model but maintains key order. It can locate a key with binary search, while inserting or removing an entry still requires shifting elements and therefore takes (O(n)) time.

Complexity

The following bounds describe an unsorted array-backed map:

Operation Best Average Worst Reason
get or membership test (O(1)) (O(n)) (O(n)) The key may be first, or may require scanning every entry
put (O(1)) (O(n)) (O(n)) Updating the first match is constant-time; finding a missing key scans the array
remove (O(n)) (O(n)) (O(n)) Searching and shifting entries are both linear
Iterate over all entries (O(n)) (O(n)) (O(n)) Every entry is visited
Access by entry index (O(1)) (O(1)) (O(1)) Array indexing is constant-time

Appending a new entry is (O(1)) amortized because a dynamic array such as a Python list occasionally resizes. Duplicate detection still costs (O(n)), so the complete put operation remains (O(n)).

Space complexity: The map owns (O(n)) key-value storage. Auxiliary working space is (O(1)), and there is no recursion stack. If the entries originate in an input list, that list contributes another (O(n)) input storage; total storage including both the input and map-owned data remains (O(n)).

Advantages and Limitations

Approach Lookup Insert or Remove Key Ordering When to Use
Unsorted array-backed map (O(n)) (O(n)) Insertion order only Small collections or simple educational implementations
Python dict (O(1)) average, (O(n)) worst (O(1)) average, (O(n)) worst Not sorted by key General-purpose production mapping
Sorted array with bisect (O(log n)) (O(n)) Sorted by key Read-heavy collections where ordered access matters
Balanced tree map (O(log n)) (O(log n)) Sorted by key Ordered production maps; Python requires a third-party implementation

Important trade-offs include:

  • Sequential locality: Scanning a contiguous backing array can be faster than following links between separately allocated nodes.

  • Preallocation: A fixed-capacity array can avoid resize allocations, but it wastes unused slots and must grow when full. A dynamic list trades occasional reallocations for amortized constant-time appends.

  • Linear scaling: Searches become a bottleneck as the map grows.

  • Insertion cost: Moving entries makes insertion and removal expensive in an array.

  • Key mutability: Mutating a key can make lookup by its original value fail and can invalidate the ordering of a sorted variant.

  • Direct addressing: If keys are bounded integer indices, a direct-address array can provide (O(1)) lookup, but consumes (O(U)) space for a key range of size (U).

Common Pitfalls

  • Duplicate keys: Decide explicitly whether insertion updates or rejects an existing key.

  • Missing values: Distinguish a missing key from a key whose stored value is None when using membership checks.

  • Edge cases: Empty maps, single-entry maps, duplicate keys, negative integer keys, and already sorted input all work; sorted input gives no speed advantage in an unsorted implementation.

  • Mutable keys: Avoid changing keys after insertion, especially in a sorted map.

  • Production choice: Use Python’s dict when average (O(1)) lookup matters. Choose a sorted array only when ordered iteration or binary search justifies its (O(n)) insertion and removal costs.

  • Common follow-up: Interviewers may ask how a sorted-array map, direct-address table, or open-addressing hash table would change the time and space trade-offs.

34

What are the average-case and worst-case time complexities of hash map operations?

A hash map uses a hash function to map keys to buckets, allowing lookups, insertions, and deletions to take O(1) time on average. If many keys collide and occupy the same bucket, an operation can degrade to O(n) in the worst case, where n is the number of stored entries.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Operation Complexity

Operation Average case Worst case Reason
Search by key O(1) O(n) Normally one bucket is examined; a collision chain may contain all entries
Insert by key O(1) O(n) Finding the key and handling a collision may require scanning the bucket
Delete by key O(1) O(n) The key must first be located in its bucket
Check key existence O(1) O(n) Uses the same lookup path as a search

These bounds assume a reasonably uniform hash function and load factor. The worst case occurs when the hash function distributes many keys into very few buckets, such as when all keys have the same hash.

Average-Case Behavior

The average O(1) lookup comes from:

  1. Computing the key’s hash value.

  2. Using that value to identify a bucket.

  3. Searching only the entries in that bucket.

With a good hash function and controlled load factor, the expected number of entries in a bucket is approximately n / m, where m is the number of buckets. As the table grows, it is resized to keep the load factor within an acceptable range.

Hash maps do not guarantee sorted key order. For example, Python’s dict preserves insertion order, but it does not support efficient ordered access by sorted key.

Worst-Case Behavior

If all n keys collide, the relevant bucket contains every entry. Searching for a missing key or resolving collisions may therefore require examining all n entries, producing O(n) time.

The worst case is rare with well-designed hash functions, but it matters when:

  • The key type has a poor or predictable hash function.

  • An attacker deliberately constructs colliding keys.

  • The hash table becomes overloaded.

Space and Resizing

  • Total space: O(n) for n key-value entries, including bucket storage and stored references.

  • Input counting: If the existing entries are treated as the input, the map’s storage is O(n) additional space; including the entries themselves, total space remains O(n).

  • Per-operation auxiliary space: Usually O(1), excluding the map’s stored data.

  • Resizing: May temporarily require O(n) additional space when a new, larger table is allocated.

Individual insertions are not strictly O(1) because an insertion can trigger resizing. However, amortized insertion time is O(1): the occasional O(n) resize is spread across many preceding insertions.

Common Pitfalls

  • Do not describe worst-case hash-map operations as O(1); O(1) is the expected or average case.

  • A resize can make one insertion expensive, but amortized insertion remains O(1).

  • Hash maps are not sorted by key; use an ordered tree map or a sorted list when ordered lookup is required.

  • Python’s dict preserves insertion order, which differs from the unordered behavior of many hash-map implementations.

  • Interviewers may ask why Python hashes keys, how collisions are resolved, and what happens when the load factor becomes too high.

35

How do Cuckoo Hashing and Linear Probing Improve Hash Maps?

Cuckoo hashing and linear probing improve hash-map performance through different collision-handling strategies. Cuckoo hashing gives each key multiple possible locations, while linear probing searches nearby slots in one table and usually benefits from good cache locality.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How They Work

  • Cuckoo hashing:

  • Computes two candidate positions for each key, usually with different hash functions.

  • If a candidate position is occupied, the existing key is displaced and moved to its alternative position.

  • If a relocation cycle forms or all candidates are blocked, the table is resized, rehashed, or configured with more choices per location.

  • A lookup checks only the key’s candidate locations rather than scanning a long cluster.

  • Linear probing:

  • Uses one primary hash position.

  • If it is occupied, checks the next slot, then the next, until finding the key or an empty slot.

  • Deleted positions require special handling so that searches are not cut short.

  • Consecutive occupied positions form a primary cluster, which can become increasingly expensive.

Performance Impact

Strategy Operation Best Average Worst Reason
Linear probing Lookup O(1) O(1 / (1 − α)) O(n) May scan an entire occupied cluster
Linear probing Insert O(1) O(1 / (1 − α)) O(n) Collisions can require scanning and shifting entries
Linear probing Delete O(1) O(1 / (1 − α)) O(n) Locating the key or backward-shifting a long cluster can be costly
Cuckoo hashing Lookup O(1) O(1) O(1) Checks two fixed candidate locations
Cuckoo hashing Insert O(1) O(1) below its practical load threshold O(n) Repeated displacement or cycle detection may be required
Cuckoo hashing Delete O(1) O(1) O(1) The key is removed directly from one candidate location

Here, α is the load factor. Under the usual uniform-hashing assumption, linear probing has expected lookup and insertion cost proportional to 1 / (1 − α). This is constant for a fixed load factor, but grows rapidly as the table approaches capacity.

Cuckoo hashing provides bounded lookup latency because it checks only a constant number of candidate locations. Classic two-choice cuckoo hashing commonly has a practical maximum load near 50%, similar to conservative linear-probing designs; bucketed or multi-choice variants can tolerate higher load factors.

Space Complexity

  • Linear probing: O(n) total space for the array, including unused capacity. It avoids the per-entry linked-node allocations used by chaining, but each slot still stores a key/value entry or an empty marker. Auxiliary space is O(1), and the input is not counted.

  • Cuckoo hashing: O(n) total space, usually with a larger constant factor because multiple tables, cells, or candidate-position metadata are maintained. Auxiliary space is O(1) for a standard bounded relocation procedure, or O(n) if the implementation records the complete displacement path. The input is not counted.

Advantages and Limitations

Strategy Advantages Limitations
Linear probing Simple implementation, low overhead, good cache locality Primary clustering, high cost near full capacity, careful deletion required
Cuckoo hashing Bounded lookup probes, fewer long collision chains, predictable read latency Extra overhead, relocation latency, possible insertion cycles, more complex deletion

Neither strategy improves every workload automatically. Linear probing is attractive when memory usage and cache performance are priorities. Cuckoo hashing is attractive when predictable lookup latency matters more than insertion consistency, relocation work, and additional metadata.

Common Pitfalls

  • High load factor: Linear probing degrades sharply as α approaches 1; resize before reaching capacity.

  • Deletion: In linear probing, replacing a deleted slot with an empty marker can break searches. Use tombstones or backward-shift deletion.

  • Duplicate keys: Update the existing value rather than inserting a second entry.

  • Poor hash functions: Both methods depend heavily on hash distribution; weak hashes can create collisions regardless of the collision strategy.

  • Adversarial inputs: Test empty tables, one element, duplicate keys, negative integer keys, full tables, and deliberately colliding keys.

  • Interview follow-ups: Be ready to explain cuckoo displacement cycles, linear-probing clusters and tombstones, load-factor effects, and why expected hash-table operations are not guaranteed to be O(1) in the worst case.

36

How does load factor affect HashMap performance?

The load factor of a hash map is the ratio of stored entries to available buckets, usually written as α = n / m. A higher load factor uses memory efficiently but increases collisions and makes lookups slower; a lower load factor reduces collisions at the cost of additional memory and occasional rehashing.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Load Factor Works

For a hash map containing n entries with m buckets:

  • Load factor: α = n / m

  • Example: 75 entries in 100 buckets gives α = 0.75.

  • Collision: Two or more keys map to the same bucket or probe sequence.

The implementation usually maintains the load factor below a configured threshold. When the number of entries exceeds that threshold, it allocates a larger bucket array and rehashes the entries.

Performance Impact

Load factor Memory usage Collision probability Typical lookup cost
Low Higher Lower Closer to O(1)
Moderate Balanced Moderate O(1) on average
High Lower Higher Noticeably slower
At or near capacity Lowest Very high May become O(n) in the worst case

For separate chaining, each bucket stores a list or tree of colliding entries. With uniform hashing, the expected number of entries examined during a lookup is approximately 1 + α.

For open addressing, all entries remain in the bucket array. A simple uniform-hashing model gives an expected probe count of approximately 1 / (1 - α), so performance deteriorates sharply as α approaches 1.

A good implementation keeps the load factor below a constant such as 0.75, making the average lookup, insertion, and deletion cost O(1).

Resizing and Amortized Cost

Resizing restores a healthy load factor by:

  1. Allocating a larger bucket array.

  2. Recalculating each entry’s bucket or probe position.

  3. Moving entries into the new structure.

One resize costs O(n + m), usually simplified to O(n) when the bucket count is proportional to the entry count. Across a sequence of insertions, however, resizing is amortized O(1) per insertion because capacity generally grows geometrically.

A smaller load factor does not make every operation faster. It also means the hash map allocates more buckets, which can increase initialization time and memory consumption.

Complexity

For a hash map with n stored entries and m buckets:

  • Best-case lookup: O(1) when the key’s bucket is found immediately.

  • Average-case lookup, insertion, and deletion: O(1 + α), or O(1) when α is bounded by a constant.

  • Worst-case lookup, insertion, and deletion: O(n) when many keys collide or follow the same probe sequence.

  • Resize: O(n + m) for one resize and amortized O(1) per insertion over repeated growth.

  • Total space: O(n + m), including stored entries and buckets; this is O(n) when m = O(n).

  • Additional working space: O(m) for the bucket array and O(1) recursion stack space.

Python’s dict maintains its internal capacity above the number of stored entries, but its exact resize thresholds and implementation details are not part of the public API.

Common Pitfalls

  • Assuming load factor alone guarantees O(1): Hash quality, collision handling, and distribution also matter.

  • Ignoring memory trade-offs: Lowering the load factor reduces collisions but increases bucket-array memory.

  • Forgetting resize costs: Individual insertions are not always O(1); resizing can temporarily cost O(n).

  • Conflating average and worst case: Average O(1) assumes a good hash function and reasonably uniform distribution; adversarial or poorly distributed keys can cause O(n) behavior.

  • Using a fixed capacity indefinitely: A map expected to grow substantially should resize dynamically.

  • Interview follow-up: Interviewers commonly ask how resize thresholds are chosen, how collisions are handled, and why average O(1) does not rule out worst-case O(n).

37

How does a Map support an LRU cache?

A Map stores cache entries by key, allowing direct retrieval without scanning the entire cache. In an LRU cache, the map connects each key to its cached value and metadata, while a doubly linked list tracks access order for constant-time promotion and eviction.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How a Map Is Used in LRU Cache

A typical web or database cache might map a request or query identifier to its response:

  • Key: URL, route, query parameters, or user ID.

  • Value: Cached response, rendered page, or query result.

  • Map operation: Check whether the key exists before performing an expensive database or network request.

  • Eviction: When the cache reaches its capacity, remove the least recently accessed entry.

A plain map finds a value by key efficiently, but it does not automatically identify which value was least recently used. LRU caches therefore combine a map with a doubly linked list. Each linked-list node stores the key, value, and links to its previous and next nodes:

  1. The map holds key -> node.

  2. The linked list orders nodes from most recently used to least recently used.

  3. A get operation moves the found node to the front.

  4. A put operation inserts a new node at the front.

  5. If capacity is exceeded, the node before the tail is removed from both structures.

The map provides key lookup, while the linked list provides ordering. Both structures have constant-time local updates.

Map and Ordered-Map Comparison

Structure Lookup Update Key ordering LRU suitability
Python dict O(1) average O(1) average Insertion order, not sorted key order Good with a separate linked list
collections.OrderedDict O(1) average O(1) average Insertion order Convenient; supports move_to_end()
Manually sorted list with bisect O(log n) O(n) due to shifting Sorted by key Poor for frequent LRU updates
Third-party SortedDict O(log n) O(log n) Sorted by key Useful when sorted-key access is required

Python has no built-in balanced-tree map. bisect works with a manually maintained sorted list, or developers can use a third-party sorted-container library.

Complexity

For a cache capacity of C:

  • Map lookup: O(1) best and average; O(n) worst case if keys experience pathological hash collisions.

  • Map insertion: O(1) amortized on average because resizing is amortized; O(n) worst case under collisions.

  • Linked-list promotion or removal: O(1) in all cases.

  • Complete get or put: O(1) best and average, O(n) worst case because of the map operation.

  • Space: O© for the map and linked-list nodes. The input is not counted, and there is no recursive stack.

Small Example Walkthrough

With capacity 2:

  1. put(1, 100) stores key 1.

  2. put(2, 200) stores key 2.

  3. get(1) returns 100 and promotes key 1 to most recently used.

  4. put(3, 300) needs space, so least recently used key 2 is evicted.

  5. get(2) returns None.

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass(slots=True)
class _Node:
    key: int
    value: int
    previous: _Node | None = None
    next: _Node | None = None


class LRUCache:
    """A fixed-capacity cache using a dict and a doubly linked list."""

    def __init__(self, capacity: int) -> None:
        if capacity <= 0:
            raise ValueError("capacity must be positive")

        self.capacity = capacity
        self._cache: dict[int, _Node] = {}

        # Sentinel nodes simplify insertion and removal at either end.
        self._head = _Node(key=0, value=0)
        self._tail = _Node(key=0, value=0)
        self._head.next = self._tail
        self._tail.previous = self._head

    def _remove(self, node: _Node) -> None:
        assert node.previous is not None
        assert node.next is not None

        node.previous.next = node.next
        node.next.previous = node.previous
        node.previous = None
        node.next = None

    def _add_to_front(self, node: _Node) -> None:
        first_node = self._head.next
        assert first_node is not None

        node.previous = self._head
        node.next = first_node
        first_node.previous = node
        self._head.next = node

    def get(self, key: int) -> int | None:
        node = self._cache.get(key)
        if node is None:
            return None

        self._remove(node)
        self._add_to_front(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        existing_node = self._cache.get(key)

        if existing_node is not None:
            existing_node.value = value
            self._remove(existing_node)
            self._add_to_front(existing_node)
            return

        if len(self._cache) >= self.capacity:
            least_recently_used = self._tail.previous
            assert least_recently_used is not None
            assert least_recently_used is not self._head

            self._remove(least_recently_used)
            del self._cache[least_recently_used.key]

        node = _Node(key=key, value=value)
        self._cache[key] = node
        self._add_to_front(node)


cache = LRUCache(capacity=2)
cache.put(1, 100)
cache.put(2, 200)
print(cache.get(1))  # 100
cache.put(3, 300)
print(cache.get(2))  # None

Common Pitfalls

  • Updating only the map: A get must also promote the entry to most recently used.

  • Removing from only one structure: Evicting an entry must remove both its node and its map entry.

  • Ignoring duplicates: Updating an existing key should refresh its value and recency without increasing cache size.

  • Choosing the wrong key: Include all inputs that affect the result, such as tenant, locale, or authorization context.

  • Using a map alone for LRU ordering: A map supports fast lookup, but maintaining explicit recency requires additional ordering logic.

38

How do maps implement adjacency lists in graphs?

A map (hash map) is the standard way to store an adjacency list, where each vertex maps to a collection of its neighboring vertices. This gives O(1) average-time access to a vertex’s neighbor collection, which is why it is the dominant implementation in Python and most languages.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Adjacency Lists Work

An adjacency list represents a graph as a mapping from each vertex to the set or list of vertices it connects to. Instead of a full n×n matrix, only existing edges are stored, making it space-efficient for sparse graphs.

  • Each key is a vertex identifier (a string, number, or object).

  • Each value is a list or set of adjacent vertices.

  • For a directed graph, the value contains only outgoing neighbors.

  • For an undirected graph, both directions are stored.

Why Maps Are Used

The map provides constant-time average access to a vertex’s neighbor collection, which is essential for graph algorithms that repeatedly traverse or modify edges.

  • O(1) average vertex lookup: Finding the neighbor collection for a vertex is a single hash lookup.

  • O(1) average insertion: Adding a new edge requires one insertion into the map (if the vertex is new) and one into the neighbor collection.

  • O(1) average deletion: Removing an edge is one removal from the neighbor collection.

  • Flexible vertex keys: Any hashable type works — strings, tuples, integers — so vertex labels need not be 0-based indices.

The time complexity for map operations is O(1) average and O(n) worst case, where n is the number of vertices, due to hash collisions. Edge-existence checks are O(1) average when the neighbor collection is a set, but O(degree) when it is a list.

Comparison with Alternatives

Implementation Vertex lookup Edge check (avg) Insert Space When to use
Map (dict) + list O(1) avg O(degree) O(1) avg O(V + E) Most cases, sparse graphs, multigraphs
Map (dict) + set O(1) avg O(1) avg O(1) avg O(V + E) When duplicates must be avoided, fast edge checks
2D array O(1) O(1) O(1) O(V²) Dense graphs, small vertex count
Array of lists O(1) O(degree) O(1) O(V + E) Vertices are 0-based integers

The array-of-lists approach is essentially the same as a map, but restricted to integer vertices. The 2D array wastes space on missing edges, so it is only better when the graph is nearly complete.

Best Practices

  • Use a set for neighbors when the graph has no duplicate edges, since it prevents duplicates automatically and gives O(1) average edge-existence checks.

  • Use a list when edge order matters (e.g., deterministic DFS traversal) or when the graph is a multigraph.

  • Initialize the map lazily: only create a neighbor collection when the first edge is added, to save space for isolated vertices.

  • In Python, use dict.get(vertex, []) or collections.defaultdict(list) / defaultdict(set) to avoid key errors.

Common Pitfalls

  • Forgetting that a map’s worst-case lookup is O(n) under heavy hash collisions, which can degrade algorithms like BFS or Dijkstra.

  • Assuming edge-existence checks are O(1) when using a list for neighbors; they are O(degree).

  • Mutating a shared neighbor list between vertices, which corrupts the graph structure.

  • Using unhashable vertex types (like lists) as keys, which raises a TypeError.

  • Not handling disconnected components when iterating over the map — always iterate over all keys, not just reachable ones.

  • Interviewers often follow up by asking how to detect a cycle or find connected components in this representation, so be ready to walk through a traversal.

39

How do maps support efficient word dictionaries and inverted indexes?

Maps support efficient lookup by associating keys with values. In a word dictionary, a word maps to metadata such as frequency or definitions; in an inverted index, a term maps to the documents containing it.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Role of Maps

A map, also called a dictionary or associative array, stores key-value pairs. Text-search systems commonly use several related structures:

  • Word dictionary: Maps a normalized word to metadata such as frequency, definition, or document count.

  • Forward index: Maps a document ID to the terms appearing in that document.

  • Inverted index: Maps a term to the documents containing it.

  • Term-position index: Records term positions as well, enabling phrase and proximity queries.

Consider the documents “maps index data” and “maps and data”:

  1. Document 0 contributes the terms maps, index, and data.

  2. Document 1 contributes maps, and, and data.

  3. The resulting mapping contains {"maps": [(0, 1), (1, 1)], "index": [(0, 1)], "data": [(0, 1), (1, 1)], "and": [(1, 1)]}.

Dictionary vs. Inverted Index

Structure Key Value Main purpose
Word dictionary Normalized word Frequency, definition, or document count Vocabulary management and exact-word lookup
Forward index Document ID Terms or term positions Describing each document’s contents
Inverted index Normalized term Posting list of document IDs Finding documents containing a term

A posting list can contain only document IDs, such as [0, 3, 7], or richer entries such as (document_id, term_frequency). Keeping one posting per document prevents repeated occurrences from creating duplicate entries.

Hash Maps vs. Ordered Maps

Property Hash map, such as Python dict Ordered/tree map
Lookup O(1) average, O(n) worst case O(log n) worst case with a balanced tree
Key order Unordered by key; dict preserves insertion order, not key order Keys remain sorted
Useful operations Exact lookup, frequency counting, grouping Sorted iteration, range queries, predecessor/successor lookup

Python has no built-in tree map. A bisect search over a manually maintained sorted list gives O(log n) key lookup, but insertion and deletion can require O(n) list movement. sortedcontainers.SortedDict is a third-party ordered-map alternative.

Complexity

Let:

  • C be the total number of corpus characters.

  • V be the number of unique normalized terms.

  • P be the total number of postings.

  • p and q be the lengths of two posting lists.

Operation Best case Average case Worst case Reason
Build an index O© O© expected O(C(V + 1)) Tokenization is linear; hash operations are expected O(1), while severe collisions can make them O(V). Posting-list appends are amortized O(1)
Look up a term O(1) O(1) expected O(V) A hash map may scan colliding entries in the worst case
Get a posting-list reference O(1) after lookup O(1) expected O(V) Finding the key dominates; obtaining the list reference is constant-time
Scan one posting list O(p) O(p) O(p) Every posting is visited
Intersect two sorted posting lists O(p + q) O(p + q) O(p + q) A two-pointer merge visits both lists once

These hash-table bounds treat term comparison as constant-time; hashing a newly constructed term additionally costs O(length of the term). Index space is O(V + P) map and posting entries, excluding the input corpus. Counting the characters stored in normalized term strings, the bound is O(C + P). The temporary per-document frequency map uses at most O(V) entries and is included in this space bound.

Best Practices and Edge Cases

  • Normalize terms consistently with operations such as case folding and, when appropriate, stemming.

  • Remove or down-weight stop words only when the use case permits it.

  • Keep posting lists sorted by document ID for efficient intersections and range queries.

  • Store positions only when phrase, highlighting, or proximity searches are required.

  • An empty corpus produces an empty map, and a document with no tokens contributes no postings.

  • Duplicate terms produce one posting per document with an increased frequency.

  • Define tokenization explicitly for negative numbers, such as deciding whether -42 is one numeric token.

  • Process documents in ascending document-ID order when possible; otherwise sort the postings afterward.

  • Disconnected-graph and cycle cases do not apply to map-backed indexes.

Common Pitfalls

  • Confusing structures: A vocabulary dictionary answers “does this word exist?”, while an inverted index answers “where does it occur?”

  • Duplicate postings: Aggregate term frequencies before adding a document’s posting.

  • Inconsistent normalization: Tokenization and normalization must use compatible rules.

  • Ignoring memory cost: Large posting lists and position data can dominate storage.

  • Assuming constant-time worst case: Hash maps are O(1) average, not guaranteed O(1).

  • Off-by-one or ordering errors: Keep document-ID conventions consistent and ensure posting lists are sorted before merging them.

  • Overflow: Python integers are arbitrary precision, but other languages need a sufficiently wide document-ID type.

  • Mutating input: Do not reorder the caller’s document collection merely to obtain sorted postings.

Common follow-up questions ask how multiple terms are combined, how phrase queries are supported, and how compressed posting lists reduce storage and query costs.

40

How to combine heaps and maps for uniform random retrieval?

A randomized multiset can combine a hash map with a min-heap of reusable slot positions. Insertion and deletion manage the map and heap in O(log n) expected time, while get_random_element() selects directly from an array of active slots in O(1) time. The probability requirement applies to element retrieval: every currently stored occurrence has the same chance of being returned; the caller controls whether insertion or deletion occurs.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Design and Invariants

  • Values array: stores the value associated with each allocated slot. Unused slots contain None.

  • Value map: maps each value to the set of slots containing it. A set allows duplicate occurrences.

  • Active-slot array: contains exactly one entry for every stored occurrence.

  • Position map: maps each active slot to its position in the active-slot array, allowing constant-time swap removal.

  • Free-slot heap: a min-heap of reusable slots. heapq implements the required min-heap.

For example, after inserting 10, 20, and 10:

  1. The active slots contain three slot IDs.

  2. The value map associates 10 with two slots and 20 with one.

  3. Deleting 20 removes its slot from the active array and adds it to the free-slot heap.

  4. The next insertion reuses that slot, keeping allocated space bounded by the maximum number of simultaneous elements.

Random retrieval chooses a uniformly random position in the active-slot array, then reads the corresponding value. Because that array contains exactly the live occurrences, each occurrence is equally likely.

Complexity

Let n be the maximum number of elements simultaneously stored.

Operation Best Average Worst
Insertion O(1) O(log n) expected O(n)
Deletion O(1) O(log n) expected O(n)
Get random element O(1) O(1) O(1)
  • Insertion: allocating a fresh slot uses an amortized O(1) list append; reusing a free slot requires heapq.heappop, which is O(log n).

  • Deletion: active-slot removal uses swap-and-pop in O(1), while adding the released slot to the heap costs O(log n).

  • Map operations: O(1) average and O(n) worst because of hash collisions.

  • Space: O(n), including the values array, maps, active-slot array, and heap; input is not counted. There is no recursion stack.

Alternative Insert Delete Random Space
Heap and map O(log n) expected O(log n) expected O(1) O(n)
Dynamic array and map O(1) amortized, expected hashing O(1) expected O(1) O(n)

If all three operations must be O(1) on average, the dynamic-array-and-map design is preferable, but it does not use a heap.

Code Example

import heapq
import random


class RandomizedMultiset:
    """Store occurrences and retrieve a uniformly random occurrence."""

    def __init__(self, random_source: random.Random | None = None) -> None:
        self._random_source = (
            random_source if random_source is not None else random.Random()
        )
        self._values: list[int | None] = []
        self._slots_by_value: dict[int, set[int]] = {}
        self._active_slots: list[int] = []
        self._active_position: dict[int, int] = {}
        self._free_slots: list[int] = []

    def insert(self, value: int) -> None:
        """Insert one occurrence of value."""
        if self._free_slots:
            slot = heapq.heappop(self._free_slots)
        else:
            slot = len(self._values)
            self._values.append(None)

        self._values[slot] = value
        self._slots_by_value.setdefault(value, set()).add(slot)

        position = len(self._active_slots)
        self._active_slots.append(slot)
        self._active_position[slot] = position

    def delete(self, value: int) -> None:
        """Remove one occurrence of value, or raise KeyError."""
        slots = self._slots_by_value.get(value)
        if not slots:
            raise KeyError(value)

        slot = slots.pop()
        if not slots:
            del self._slots_by_value[value]

        # Remove the slot by swapping it with the final active slot.
        position = self._active_position.pop(slot)
        last_position = len(self._active_slots) - 1

        if position != last_position:
            moved_slot = self._active_slots[last_position]
            self._active_slots[position] = moved_slot
            self._active_position[moved_slot] = position

        self._active_slots.pop()
        self._values[slot] = None
        heapq.heappush(self._free_slots, slot)

    def get_random_element(self) -> int:
        """Return one uniformly random stored occurrence."""
        if not self._active_slots:
            raise IndexError("cannot sample an empty multiset")

        position = self._random_source.randrange(len(self._active_slots))
        slot = self._active_slots[position]
        value = self._values[slot]
        assert value is not None
        return value

    def __len__(self) -> int:
        return len(self._active_slots)


def example() -> None:
    """Insert, delete, and sample from a randomized multiset."""
    elements = RandomizedMultiset(random.Random(1))
    elements.insert(10)
    elements.insert(20)
    elements.insert(10)
    elements.delete(20)

    print(elements.get_random_element())  # 10
    print(len(elements))                  # 2


if __name__ == "__main__":
    example()

Common Pitfalls

  • Sampling from the allocated-slot array can select deleted or unused slots; sample only from _active_slots.

  • list.pop(0) and list.insert(0, value) are O(n); use swap-and-pop.

  • A map cannot directly represent duplicate values; map each value to a set of slots.

  • Deletion removes one occurrence; duplicate values remain independently retrievable until all occurrences are removed.

  • Sampling an empty multiset raises IndexError, and deleting an absent value raises KeyError. With one element, retrieval always returns it, and deleting it empties the structure.

  • Negative integer values are supported normally.

  • Map operations are O(1) on average, not guaranteed O(1) in the worst case.

Interview Tips

Expect follow-up questions about unique values versus duplicates, worst-case hash-map behavior, why free slots are reused, and whether O(1) average insertion and deletion are required. Also explain that uniform retrieval means equal probability among active elements—not equal probability of invoking each API method.

41

How do I implement top-k frequency counting with Counter?

A Counter map records how often each element occurs, while a bounded min-heap retains only the k most frequent elements. This avoids sorting every distinct element when only a small top-k result is required.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. Build a Counter from the input. It maps each hashable element to its occurrence count.

  2. Iterate over the distinct elements and maintain a heap containing at most k candidates.

  3. Treat the heap as a min-heap ordered by frequency:

  4. The root is the least frequent retained element.

  5. A new candidate replaces the root only when it is more frequent.

  6. For equal frequencies, break ties by first appearance in the input.

  7. Sort the retained candidates by decreasing frequency before returning them.

The implementation uses (-order) as the heap tie-breaker so the least desirable candidate—later first appearance—occupies the root.

Complexity

Let:

  • n be the number of input elements.

  • u be the number of distinct elements.

  • h = min(k, u) be the maximum number of heap entries.

  • k > 0 for the bounds below.

Approach Average time Auxiliary space When to use
Count and sort distinct elements O(n + u log u) O(u) All elements must be ranked
Count and maintain a bounded heap O(n + u log(h + 1)) O(u) Only the top k elements are needed
  • Counting: Best and average case are O(n) because each Counter update takes expected O(1) time. Worst case is O(n²) under pathological hash collisions, where an update can take O(n).

  • Best-case total: O(n + u) for either approach when the retained frequencies and ordering permit linear-time heap updates and ordering.

  • Worst-case total: O(n² + u log u) for count-and-sort and O(n² + u log(h + 1)) for the bounded heap, including pathological hash collisions.

  • Heap selection: Average and worst case are O(u log(h + 1)); when k = 1, this becomes O(u).

  • Space: O(u) auxiliary space, including the Counter, heap, and result. The input is not counted, and the recursion stack is O(1).

Example Walkthrough

For ["a", "b", "a", "c", "b", "a"] and k = 2:

Element Count Heap action
a 3 Insert a
b 2 Insert b; b is currently the root
c 1 Ignore because it does not beat the root

The result is [("a", 3), ("b", 2)].

Code Example

from collections import Counter
from collections.abc import Iterable
import heapq


def most_frequent(
    elements: Iterable[object], k: int
) -> list[tuple[object, int]]:
    """Return the k most frequent elements with their counts."""
    if k <= 0:
        return []

    counts: Counter[object] = Counter(elements)
    heap: list[tuple[int, int, object]] = []

    for order, (value, count) in enumerate(counts.items()):
        # Earlier first appearances are preferred when counts are equal.
        entry = (count, -order, value)

        if len(heap) < k:
            heapq.heappush(heap, entry)
        else:
            root_count, root_order, _ = heap[0]
            if (count, -order) > (root_count, root_order):
                heapq.heapreplace(heap, entry)

    ranked = sorted(heap, key=lambda entry: (-entry[0], -entry[1]))
    return [(value, count) for count, _, value in ranked]


values = ["a", "b", "a", "c", "b", "a"]
print(most_frequent(values, 2))
# [('a', 3), ('b', 2)]

Common Pitfalls

  • Empty input: The function returns an empty list because the Counter is empty.

  • One element: If k >= 1, that element is returned with its occurrence count.

  • Zero or negative k: Return an empty list rather than attempting heap operations.

  • Fewer than k distinct elements: Return every distinct element, ordered by frequency.

  • Duplicates: Each occurrence contributes to the corresponding Counter count.

  • Negative numbers: They are valid keys; frequency ordering is independent of their numeric sign.

  • Already sorted input: Input order does not affect counts, but it can change which equal-frequency element wins because the tie-break uses first appearance.

  • Hashability: Elements passed to Counter must be hashable.

  • Tie handling: This implementation consistently prefers the element that appeared first rather than relying on unspecified ordering.

  • Production shortcut: Counter.most_common(k) already provides the top-k behavior and orders equal counts by first encounter. It delegates to heapq.nlargest, which may use sorting instead of a heap when k is at least the number of distinct items.

42

How do you solve Sliding Window Maximum using heaps?

Sliding Window Maximum can be found by maintaining a max-heap of the current window’s elements. Because Python’s heapq implements a min-heap, store negated values and remove expired indices lazily from the heap root.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Heap-Based Approach

For each element at index right:

  1. Insert (-value, right) into the heap.

  2. Calculate the window’s left boundary: left = right - window_size + 1.

  3. Remove heap-root entries whose indices are smaller than left.

  4. Once the window is complete, the heap root represents its maximum value.

  5. Occasionally compact the heap to prevent expired, non-root entries from accumulating.

The tuple (-value, index) gives the desired max-heap ordering while allowing duplicate values because indices are unique.

Example Walkthrough

For values = [1, 3, -1, -3, 5, 3] and window_size = 3:

Right index Current window Maximum Output
0 [1] — —
1 [1, 3] — —
2 [1, 3, -1] 3 3
3 [3, -1, -3] 3 3
4 [-1, -3, 5] 5 5
5 [-3, 5, 3] 5 5

The result is [3, 3, 5, 5].

Complexity

Let n be the number of elements and k the window size, with 1 <= k <= n.

Approach Best time Average time Worst time Auxiliary space When to use
Brute force O(nk) O(nk) O(nk) O(1) Simple baseline when windows are small
Heap-based O(n log k) O(n log k) O(n log k) O(k) When the solution must use a heap or retain index metadata
  • Time: Each element is inserted and removed at most once, requiring O(log k) per heap operation for k >= 2. For k = 1, the time is O(n).

  • Space: Between compactions, the heap contains at most 2k + 1 entries, so auxiliary space is O(k), excluding the input and O(n − k + 1) output. The implementation is iterative and uses no recursion stack.

  • Heap operations: heappush and heappop are O(log k), while reading the root is O(1).

  • Compaction: heapify is O(k), not O(k log k), because bottom-up heap construction performs work proportional to subtree heights, which sum to O(k). Each rebuild discards more than k stale entries, making its O(k) cost O(1) amortized per discarded entry.

Code Example

from heapq import heapify, heappop, heappush


def sliding_window_max(
    values: list[int],
    window_size: int,
) -> list[int]:
    """Return the maximum value of every full window."""
    if window_size <= 0:
        raise ValueError("window_size must be positive")
    if not values:
        return []
    if window_size > len(values):
        return []

    result: list[int] = []
    max_heap: list[tuple[int, int]] = []

    for right, value in enumerate(values):
        # Negation turns Python's min-heap into a max-heap.
        heappush(max_heap, (-value, right))

        left = right - window_size + 1

        # Remove expired entries whenever they reach the root.
        while max_heap and max_heap[0][1] < left:
            heappop(max_heap)

        # Only output a result for a complete window.
        if left >= 0:
            result.append(-max_heap[0][0])

            # Prevent expired entries below the root from accumulating.
            if len(max_heap) > 2 * window_size:
                max_heap = [
                    entry for entry in max_heap
                    if entry[1] >= left
                ]
                heapify(max_heap)

    return result


print(sliding_window_max([1, 3, -1, -3, 5, 3], 3))
# Output: [3, 3, 5, 5]

Common Pitfalls

  • Using heapq without negation: heapq is a min-heap, so store -value to obtain maximum-first ordering.

  • Ignoring incomplete windows: Do not emit a result while left < 0.

  • Allowing unbounded stale entries: Removing only expired roots preserves correctness, but hidden expired entries can accumulate. Periodic compaction keeps auxiliary space O(k).

  • Losing duplicate values: Store the index alongside the value so equal values remain distinguishable.

  • Invalid window sizes: Reject window_size <= 0; an empty input or a window larger than the input produces no complete windows.

  • Special input shapes: One element works when window_size = 1. Negative, duplicate, sorted, and reverse-sorted values require no special handling.

  • Mutating the input: The implementation creates a separate heap and does not modify values.

A common follow-up asks for an O(n) solution; that is typically implemented with a monotonic deque rather than a heap.

43

How do you find top K frequent words using a heap and map?

Use a frequency map to count occurrences, then a bounded min-heap to retain the best K distinct words. The heap root represents the weakest retained candidate, allowing efficient replacement as frequencies are processed.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

  1. Store each word’s frequency in a hash map. Python’s Counter is a convenient map implementation.

  2. Maintain a min-heap containing at most K (frequency, word) pairs.

  3. For each distinct word:

  4. Insert it if the heap contains fewer than K entries.

  5. Otherwise, replace the heap root when the candidate has a higher frequency.

  6. Sort the selected words by descending frequency, breaking ties by descending lexicographic order.

The tie policy used here is: when frequencies are equal, lexicographically larger words are preferred. A different policy can be chosen if the problem specifies one.

Map Choice

Map type Lookup/update Ordering When to use
Hash map (dict or Counter) O(1) average, O(n) worst case with pathological collisions Unordered by key Frequency counting and top-K selection
Balanced tree map O(log n) worst case Sorted by key Ordered key-range queries or sorted iteration

Python has no built-in tree map. A bisect-based sorted list is an option, although insertion or deletion can take O(n) because elements must be shifted; a third-party sorted container is another option.

Complexity

Let:

  • n = total number of words.

  • u = number of distinct words.

  • h = min(K, u) = maximum heap size.

Operation Time Space Reason
Build frequency map O(n) average; O(n²) worst case with pathological hash collisions O(u) Each token is counted once; distinct words require map entries.
Maintain bounded heap O(u log(h + 1)) O(h) Each candidate causes at most one heap push or replacement costing O(log h).
Sort selected words O(h log h) O(h) Sorting h selected words uses comparison sorting and may allocate O(h) space.

Overall:

  • Best case: O(n + u log(h + 1)).

  • Average case: O(n + u log(h + 1)) expected.

  • Worst case: O(n² + u log(h + 1)) under adversarial hash collisions.

  • Auxiliary space: O(u), including the map and heap; the input is not counted. Including the input, it is O(n + u).

  • Recursion stack: O(1) because the implementation is iterative.

Although heapq.heapify is O(n), this implementation maintains a bounded heap with individual updates. Heap construction is linear because the maximum sift-down distance decreases with each tree level, so the total work sums to O(n), not O(n log n).

Example Walkthrough

For:

["apple", "banana", "apple", "orange", "banana", "apple"], K = 2

The frequency map is:

apple → 3
banana → 2
orange → 1

The heap evolves as follows:

Candidate Heap state Action
apple, frequency 3 [(3, apple)] Insert
banana, frequency 2 [(2, banana), (3, apple)] Insert
orange, frequency 1 Unchanged Reject because 1 < 2

The final result is ["apple", "banana"].

Code Example

from collections import Counter
from heapq import heappush, heapreplace


def top_k_frequent_words(words: list[str], k: int) -> list[str]:
    """Return up to k distinct words ordered by descending frequency."""
    if k <= 0:
        return []

    frequency_map = Counter(words)
    heap: list[tuple[int, str]] = []

    for word, frequency in frequency_map.items():
        if len(heap) < k:
            heappush(heap, (frequency, word))
            continue

        lowest_frequency, weakest_word = heap[0]

        # Equal frequencies prefer the lexicographically larger word.
        if frequency > lowest_frequency or (
            frequency == lowest_frequency and word > weakest_word
        ):
            heapreplace(heap, (frequency, word))

    return sorted(
        (word for frequency, word in heap),
        key=lambda word: (frequency_map[word], word),
        reverse=True,
    )


print(
    top_k_frequent_words(
        ["apple", "banana", "apple", "orange", "banana", "apple"],
        2,
    )
)
# Expected output: ['apple', 'banana']

Common Pitfalls

  • Ignoring ties: Confirm whether equal-frequency words should be ordered lexicographically, by first occurrence, or returned in any order.

  • Using a max-heap incorrectly: heapq is a min-heap. The root is the weakest retained entry, making it the correct candidate for replacement.

  • Assuming heapify is O(n log n): It is O(n) because most nodes perform only a small amount of sift-down work.

  • Edge cases: The function handles empty input, K <= 0, one distinct word, duplicates, negative words as strings, and K greater than the number of distinct words.

  • Normalization: Matching is case-sensitive and punctuation-sensitive unless the input is explicitly normalized.

  • Input mutation: The function does not modify words.

44

How to design a leaderboard system with Heaps and Maps?

A leaderboard system can combine a hash map for current player scores with a binary max-heap for efficient top-K retrieval. Versioned heap entries and lazy deletion make score updates efficient while preventing stale or duplicate results.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Structure Role Operation
scores hash map Current player -> score O(1) average lookup/update
versions hash map Current player -> version O(1) average lookup/update
heapq min-heap (-score, player, version) entries O(log H) push/pop
  • Update: Store the score and a new version in the maps, then push (-score, player, version) onto the heap.

  • Top-K: Pop entries in descending-score order. Accept an entry only when its version matches the player’s current version; otherwise discard it as stale. Ties are ordered alphabetically by player.

  • Rank: Scan the score map and count players with a strictly higher score. This produces standard competition ranking: 1, 2, 2, 4.

Exact rank queries become expensive when frequent. An order-statistic balanced tree can support rank queries and updates in O(log n), but Python has no built-in tree map. A maintained sorted list with bisect gives O(log n) rank searches but O(n) updates; SortedContainers is a third-party alternative.

Complexity

Let n be the current player count, H the heap size, u the number of score updates, and s the stale entries encountered during a top-K call.

  • Update: Best O(1), average O(1) for random insertion order, and worst O(log(H+1)); O(1) additional working space.

  • Top-K: O((k + s) log(H+1)) time. With no stale entries this is O(k log(H+1)); the worst case is O(H log(H+1)). Temporary space is O(k).

  • Rank: O(n) time and O(1) additional space.

  • Persistent space: O(n + H), at most O(n + u). Stored leaderboard state is counted, caller-provided input and returned output are not, and the recursion stack is O(1) because the implementation is iterative.

Walkthrough

  1. Update Alice to 100, creating version 0.

  2. Update Bob to 90, creating version 0 for Bob.

  3. Update Alice to 110, creating version 1; Alice’s version 0 entry is now stale.

  4. A top-2 query accepts Alice’s version 1, discards Alice’s version 0, and then accepts Bob.

Code Example

import heapq


class Leaderboard:
    """Maintain scores with a hash map and a versioned lazy-deletion heap."""

    def __init__(self) -> None:
        self.scores: dict[str, int] = {}
        self.versions: dict[str, int] = {}
        self.heap: list[tuple[int, str, int]] = []
        self.next_version: int = 0

    def update_score(self, player: str, score: int) -> None:
        """Store a new score and add a uniquely versioned heap entry."""
        version = self.next_version
        self.next_version += 1
        self.scores[player] = score
        self.versions[player] = version
        heapq.heappush(self.heap, (-score, player, version))

    def get_top_k(self, k: int) -> list[tuple[str, int]]:
        """Return up to k current players ordered by score, then player name."""
        if k <= 0:
            return []

        top_k: list[tuple[str, int]] = []
        valid_entries: list[tuple[int, str, int]] = []

        while len(top_k) < k and self.heap:
            entry = heapq.heappop(self.heap)
            negative_score, player, version = entry

            if (
                self.versions.get(player) == version
                and self.scores.get(player) == -negative_score
            ):
                top_k.append((player, -negative_score))
                valid_entries.append(entry)
            # Stale entries are discarded rather than restored.

        for entry in valid_entries:
            heapq.heappush(self.heap, entry)

        return top_k

    def get_rank(self, player: str) -> int:
        """Return a 1-based rank, with tied players sharing a rank."""
        if player not in self.scores:
            return -1

        score = self.scores[player]
        return 1 + sum(other_score > score for other_score in self.scores.values())


if __name__ == "__main__":
    leaderboard = Leaderboard()
    leaderboard.update_score("Alice", 100)
    leaderboard.update_score("Bob", 90)
    leaderboard.update_score("Alice", 110)

    print(leaderboard.get_top_k(2))  # [('Alice', 110), ('Bob', 90)]
    print(leaderboard.get_rank("Bob"))  # 2

Common Pitfalls

  • Stale or duplicate entries: A version map is the leaderboard equivalent of a visited set; without it, repeated updates can return a player more than once.

  • Edge cases: Empty and one-player leaderboards work; k <= 0 returns an empty list; unknown players have rank -1. Duplicate scores share a rank, negative scores are valid, and input order—including already sorted input—does not affect correctness. Graph connectivity and cycles are not applicable.

  • Rank off-by-one: Ranks start at 1, and only strictly higher scores advance the rank.

  • Heap growth: Rebuild the heap from current map entries when stale entries dominate. heapq.heapify is O(n), not O(n log n), because it performs bottom-up sift-down operations.

  • Mutation and overflow: The example does not mutate a caller-owned score collection and restores valid heap entries after top-K queries. Python integers do not overflow, but other languages should use an adequately wide integer type.

  • Interview follow-up: Discuss how the design changes when exact-rank queries dominate top-K queries or when updates must be immediately reflected in every replica.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 44 Heaps and Maps answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects