Heap / Priority Queue: pattern and problems

Step 1 Understand it

Remember it by
'K largest' → keep a min-heap of size k; the smallest in it is the k-th largest.

Watch it happen

AnimationA heap keeps the biggest (or smallest) item on top

Read the animation as text

Each turn, smash the two heaviest stones. A max-heap keeps the heaviest at the top, always. Python's heapq is a min-heap, so the code stores −weight.
heapify arranges them as a tree where every parent is heavier than its children — in O(n). The heaviest, 8, is at the top.
Pop twice: 8 and 7, the two heaviest. After each pop the heap moves the next heaviest to the top, in O(log n).
8 − 7 = 1: push 1 back. It goes in at the bottom and swaps upwards only while it is heavier than its parent: O(log n).
Pop twice: 4 and 2, the two heaviest. After each pop the heap moves the next heaviest to the top, in O(log n).
4 − 2 = 2: push 2 back. It goes in at the bottom and swaps upwards only while it is heavier than its parent: O(log n).
Pop twice: 2 and 1, the two heaviest. After each pop the heap moves the next heaviest to the top, in O(log n).
2 − 1 = 1: push 1 back. It goes in at the bottom and swaps upwards only while it is heavier than its parent: O(log n).
Pop twice: 1 and 1, the two heaviest. After each pop the heap moves the next heaviest to the top, in O(log n).
1 and 1 are equal: both are destroyed, nothing goes back.
One stone left: answer 1. Each turn costs O(log n) instead of re-sorting the whole pile.

The idea

A heap always gives you the smallest item (Python's heapq is a min-heap) in O(log n). Use it when you repeatedly need the current best: the k largest, the closest, the next task, the median of a stream.

Picture it

flowchart LR
  X["next number x"] --> P["push x into the min-heap"]
  P --> Q{"heap size > k?"}
  Q -->|"yes"| D["pop the smallest"] --> T["heap[0] = k-th largest so far"]
  Q -->|"no"| T
  T --> X

The heap keeps only the k biggest numbers seen; its smallest member is the answer.

Analogy

A hospital waiting room: whoever is most urgent goes next, no matter when they arrived. A new patient slots in by urgency.

Where the analogy breaks

A waiting room shows everyone in order. A heap only promises the top item; the rest are only partly sorted, which is what makes it fast.

More detail

What it is

Imagine a VIP line at a club. Normal queues are 'First Come, First Served'. But in a Priority Queue (which is usually built using a Heap), the 'most important' person always gets pulled to the front immediately, no matter when they arrived! A Heap is a magical tree structure where the smallest (Min-Heap) or largest (Max-Heap) element is ALWAYS sitting perfectly at the very top, ready to be grabbed.

When to use it

When you need to repeatedly find the minimum or maximum element in a dynamically changing dataset.
When a problem asks for the 'Top K' or 'Kth Largest/Smallest' elements.
When implementing advanced algorithms like Dijkstra's Shortest Path.

How it works

Under the hood, a Heap is just an array disguised as a Binary Tree. When you add() a new item, it's placed at the bottom and 'bubbles up' to its correct spot depending on its priority. When you poll() (remove) the top item, the bottom item is moved to the top and 'bubbles down'. Both operations take exactly O(log N) time, which is much faster than re-sorting an entire array every time!

Example walkthrough

Input: nums = [3,2,1,5,6,4], k = 2 (Find 2nd largest)

Create Min-Heap of size 2.
Insert 3, then 2. Heap=[2, 3].
Insert 1. Heap=[1, 2, 3]. Size > 2, so pop smallest (1). Heap=[2, 3].
Insert 5, pop 2. Heap=[3, 5].
Insert 6, pop 3. Heap=[5, 6].
Insert 4, pop 4. Heap=[5, 6]. Done! Top of heap is 5, which is the 2nd largest!

Result: 5

Related patterns

Two Heaps: Using a Min-Heap and Max-Heap together to instantly find the Median of a data stream.

Step 2 Recognise it

Words that signal it

'K largest / smallest / closest / most frequent'
'Stream' of numbers arriving one at a time
'Median' of a growing list (two heaps)
'Always process the cheapest / earliest / biggest next'

Don't confuse it with

Sorting: Sorting needs all the data and costs O(n log n). A heap of size k handles a stream and costs O(n log k).
Binary Search: Binary search finds a position in sorted data; a heap keeps the best few as data changes.

Gut check

Do I keep needing the current smallest or largest as things change? → heap.

How to recognise it in an interview

The problem literally uses the words 'Top K', 'K Closest', or 'Kth Largest'.

Step 3 The template

The general shape. Adapt it to each problem rather than learning one solution per problem.

python

import heapq

def k_largest(nums, k):
    heap = []                          # min-heap holding the k largest so far
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)        # throw away the smallest
    return heap[0]                     # the k-th largest

# max-heap trick: push -x, and negate again when you pop

The same template in Java

text

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // Min-Heap keeps exactly k largest elements seen so far
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.add(num);
            if (minHeap.size() > k) {
                minHeap.poll(); // Kick out the smallest guy
            }
        }
        return minHeap.peek(); // The k-th largest is sitting at the absolute top
    }
}

TimeO(log n) per push or pop; O(n log k) for top-k

SpaceO(k)

Common mistakes

Forgetting heapq is a min-heap: push -x for a max-heap.
Using a max-heap of everything for 'k largest' instead of a min-heap of size k.
Pushing tuples whose second item can't be compared: add a tie-breaker, e.g. (distance, index, point).
Forgetting that PriorityQueue in Java is a Min-Heap by default, not a Max-Heap!

Step 4 Watch it run

Two problems, traced step by step exactly as the code runs.

Easy example: Last Stone Weight (max-heap)

Input: stones = [2, 7, 4, 1, 8, 1]

two heaviest	result	stones left (heaviest first)
8 and 7	1 goes back	[4, 2, 1, 1, 1]
4 and 2	2 goes back	[2, 1, 1, 1]
2 and 1	1 goes back	[1, 1, 1]
1 and 1	both destroyed	[1]

Result: 1

Notice: Each round needs the two heaviest stones — exactly what a heap gives you in O(log n).

python

import heapq

def last_stone_weight(stones):
    heap = [-s for s in stones]        # negate for a max-heap
    heapq.heapify(heap)
    while len(heap) > 1:
        a, b = -heapq.heappop(heap), -heapq.heappop(heap)
        if a != b:
            heapq.heappush(heap, -(a - b))
    return -heap[0] if heap else 0

Medium example: Kth Largest Element in an Array

Input: nums = [3, 2, 1, 5, 6, 4], k = 2

x	action	heap (the k largest)
3	push 3	[3]
2	push 2	[2, 3]
1	push 1, size > 2 → pop smallest (1)	[2, 3]
5	push 5, size > 2 → pop smallest (2)	[3, 5]
6	push 6, size > 2 → pop smallest (3)	[5, 6]
4	push 4, size > 2 → pop smallest (4)	[5, 6]

Result: 5

Notice: The heap never holds more than k numbers, so each step costs O(log k), not O(log n).

python

import heapq

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

Step 5 Practise

Read each question and say the pattern and the trick out loud before you open the answer. Then solve it on LeetCode. Tick a problem once you've solved it on your own: it comes back for review tomorrow, then after 3, 7, 14 and 30 days, then every month, on the DSA page.

Easy

Mark "Kth Largest Element In a Stream" as solved Kth Largest Element In a Stream Easy

Numbers arrive one at a time; after each, report the k-th largest so far.

Show answer

Technique: Min-heap of size k

The clue: 'K-th largest' in a 'stream'.

The trick: Keep the k largest in a min-heap; its top is the answer.
Mark "Last Stone Weight" as solved Last Stone Weight Easy

Repeatedly smash the two heaviest stones together; return what's left.

Show answer

Technique: Max-heap

The clue: 'The two heaviest' over and over.

The trick: Use a max-heap (negative values in Python); pop two, push back the difference.

Medium

Mark "K Closest Points to Origin" as solved K Closest Points to Origin Medium

Return the k points closest to (0, 0).

Show answer

Technique: Heap of size k (or quickselect)

The clue: 'K closest' = top k by distance.

The trick: Keep a max-heap of size k on squared distance (no need for square roots).
Mark "Kth Largest Element In An Array" as solved Kth Largest Element In An Array Medium

Find the k-th largest number in an unsorted array.

Show answer

Technique: Min-heap of size k (or quickselect)

The clue: 'K-th largest'.

The trick: A size-k min-heap gives O(n log k); quickselect averages O(n).
Mark "Task Scheduler" as solved Task Scheduler Medium

Tasks must wait n intervals before repeating; find the fewest intervals to finish them all.

Show answer

Technique: Max-heap + cooldown queue (or a counting formula)

The clue: Always run the most frequent remaining task next.

The trick: Pop the most frequent task, put it in a cooldown queue with its ready time, and push it back when ready.
Mark "Design Twitter" as solved Design Twitter Medium

Design follow, unfollow, post and a feed of the 10 most recent tweets from people you follow.

Show answer

Technique: Merge k sorted lists with a heap

The clue: '10 most recent' across many people's sorted tweet lists.

The trick: Each user's tweets are sorted by time; push each followee's newest tweet into a heap and pop 10 times.

Hard

Mark "Find Median From Data Stream" as solved Find Median From Data Stream Hard

Add numbers one at a time and return the median at any moment.

Show answer

Technique: Two heaps

The clue: 'Median' of a 'stream'.

The trick: A max-heap for the lower half and a min-heap for the upper half, kept balanced; the median is at their tops.

What to say in the interview

'Sorting takes O(N log N). Since we only care about the top K elements, I can use a Min-Heap of size K to optimize this to O(N log K).'

Follow-up prep

How do you make a Max-Heap in Java? (Hint: Collections.reverseOrder()).