Overview

A heap is a complete binary tree stored in an array where every parent is no larger than its children (a min-heap) or no smaller (a max-heap). It does not keep everything sorted — only the root is guaranteed to be the extreme — and that relaxed promise is what lets push and pop run in O(log n).

Whenever a problem repeatedly asks for "the smallest so far", "the k largest" or "the next event to happen", reach for a heap. Python's heapq is a min-heap (negate values for a max-heap); C++ std::priority_queue is a max-heap by default (pass greater<> for a min-heap).

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
Peek min/maxO(1)
Push / popO(log n)
Build from n itemsO(n)
Top-k of n itemsO(n log k)

Patterns to recognise

Top-k

Use it for: k-th largest, k closest points, top-k frequent.

Maintain a heap of size k with the "worst kept" item at the root.

K-way merge

Use it for: Merge k sorted lists, smallest range covering k lists.

Push the head of each list; pop the smallest and push its successor.

Greedy scheduling

Use it for: Task scheduler, IPO, meeting rooms.

Always process the most urgent or most profitable available item next.

Code template

K-th largest element with a size-k min-heap
import heapq


def find_kth_largest(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)      # drop the smallest
    return heap[0]

Common mistakes

  • Mixing up default directions: heapq is a min-heap, priority_queue is a max-heap.
  • Pushing tuples whose second element is not comparable — add a counter as a tie-breaker.
  • Using a heap when you need to search or remove arbitrary elements; use a balanced BST (std::set) instead.

Quick check

Three questions on Heaps. Get all three right to earn +15 XP.

  1. In a min-heap, where is the smallest element?

  2. Pushing to or popping from a heap of n elements costs:

  3. To find the k largest elements of a stream, you keep:

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Heaps?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor