Heap / Priority Queue Pattern

A Heap (or Priority Queue) is a specialized tree-based data structure that satisfies the heap property: in a min-heap, any parent node has a value less than or equal to its children, meaning the absolute minimum value is always at the root. In a max-heap, parent nodes are greater than or equal to their children, meaning the maximum value is always at the root.

Heaps allow us to find the min/max element in $O(1)$ time and add new elements or extract the root in $O(log N)$ time.

The Core Concept: Min Heap Mechanics (Insertion)

To understand this concept deeply, let's explore Min Heap Mechanics (Insertion & Sift-Up).

Problem Statement: Given a valid Min Heap, insert a new element and restore the heap property.

Naive Unsorted Array — $O(N)$ Extraction

A naive priority queue uses a simple unsorted array.

Insertion: Append the new element to the end of the array, which takes $O(1)$ time.
Extraction: Scan the entire array to locate the minimum value, swap it with the last element, and pop it off the end. This takes $O(N)$ time.

class UnsortedArrayPQ:
    def __init__(self):
        self.queue = []
        
    def insert(self, val: int):
        self.queue.append(val)   # O(1) time
        
    def extract_min(self) -> int:
        if not self.queue:
            return None
        min_idx = 0
        for i in range(1, len(self.queue)):
            if self.queue[i] < self.queue[min_idx]:
                min_idx = i
        return self.queue.pop(min_idx)  # O(N) time

While insertion is fast, repeatedly extracting the minimum takes $O(N)$ time, which makes this approach too slow for streaming or sorting.

The Binary Heap Breakthrough — $O(log N)$

A Binary Heap is a complete binary tree mapped efficiently into an array where:

For any node at index i, its parent is at (i - 1) // 2, and its children are at 2*i + 1 and 2*i + 2.
We maintain parent-child ordering constraints (min-heap: parent $le$ $l e$ children) during mutations:
- Sift-Up (Insertion): Append the element at the end of the array. Compare it with its parent; if it is smaller, swap them. Repeat this until it reaches the root or the parent is smaller.
- Sift-Down (Extraction): Replace the root with the last element. Compare the new root with its children and swap with the smaller child until the ordering is restored.

Sorting constraint bubble-up/down takes only $O(log N)$ steps.

Step-by-Step Traversal

Let's trace the insertion of value 2 into a Min Heap: [3, 8, 10, 15, 20, 25].

Step 1: Initial Heap

We start with a valid min-heap of size 6.

INITInitial Min Heap before inserting: [3, 8, 10, 15, 20, 25].1 / 11

Binary Tree View

Flat Array representation

scroll to zoom · drag to pan

111

Step 2: Append Element

We push the new element 2 to the end of the heap at index 6.

PUSHInsert 2: Push new element 2 to the end of the heap at index 6.1 / 10

Binary Tree View

Flat Array representation

scroll to zoom · drag to pan

110

Step 3: First Sift-Up Comparison

We compare the new element at index 6 (value 2) with its parent at index 2 (value 10).
Since child $2 < ext{parent } 10$ , we violate the min-heap property.

COMPARESift Up: Compare current element at index 6 (value 2) with parent at index 2 (value 10).1 / 9

Binary Tree View

Flat Array representation

scroll to zoom · drag to pan

We swap them to restore order. Node 2 is now at index 2, and node 10 is at index 6.

SWAPSwapped elements. Now index 2 has value 2 and index 6 has value 10.1 / 7

Binary Tree View

Flat Array representation

scroll to zoom · drag to pan

We update our current index tracking pointer to index 2.

SIFT_UPUpdate current index i = parent index 2.1 / 6

Binary Tree View

Flat Array representation

scroll to zoom · drag to pan

Step 4: Second Sift-Up Comparison

We compare our element at index 2 (value 2) with its new parent at index 0 (value 3).
Since child $2 < ext{parent } 3$ , we swap them.

COMPARESift Up: Compare current element at index 2 (value 2) with parent at index 0 (value 3).1 / 5

Binary Tree View

Flat Array representation

scroll to zoom · drag to pan

Swapped. Node 2 is now at the root (index 0), and node 3 is at index 2.

SWAPSwapped elements. Now index 0 has value 2 and index 2 has value 3.1 / 3

Binary Tree View

Flat Array representation

scroll to zoom · drag to pan

We update our index pointer to index 0.

SIFT_UPUpdate current index i = parent index 0.1 / 2

Binary Tree View

Flat Array representation

scroll to zoom · drag to pan

Step 5: Done

Since the element has reached index 0 (the root), it has no more parents. The insertion is complete.

DONEInsertion complete: element has reached the root of the heap.1 / 1

Binary Tree View

Flat Array representation

scroll to zoom · drag to pan

Code Implementation

class MinHeap:
    def __init__(self):
        self.heap = []
        
    def insert(self, val: int):
        self.heap.append(val)
        self.sift_up(len(self.heap) - 1)
        
    def sift_up(self, i: int):
        while i > 0:
            parent = (i - 1) // 2
            # If the child value is smaller than its parent, swap them
            if self.heap[i] < self.heap[parent]:
                self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
                i = parent   # Move index to parent
            else:
                break

Time Complexity: $O(log N)$ — in the worst case, the sift-up process travels from the leaf node to the root, which is equal to the height of the tree ( $log_2 N$ ). Space Complexity: $O(1)$ — in-place swaps on the array representing the heap.

Core Variations

1. Top-K Elements

Find the $K$ largest (or smallest) elements from an unsorted stream of data.

Approach: Maintain a Min Heap of size $K$ to find the $K$ largest. If size exceeds $K$ , pop the root. The min-heap root always holds the $K$ -th largest element.
Examples: Kth Largest Element in an Array, K Closest Points to Origin.

2. Merge K Sorted Lists

Merge $K$ sorted arrays/lists into a single sorted output.

Approach: Push the first element of each list into a Min Heap. Pop the minimum element, and push the next element of that list into the heap. Repeat until the heap is empty.
Example: Merge K Sorted Lists.

3. Two Heaps (Streaming Median)

Find the median of a stream of numbers in $O(1)$ time.

Approach: Use a Max Heap to store the lower half of numbers, and a Min Heap to store the upper half. Keep the sizes balanced (difference $le 1$ ). The median is either the root of the larger heap or the average of both roots.
Example: Median from Data Stream.

When Do I Use This?

Identify these signals:

The problem asks for the Top K largest, smallest, closest, or most frequent items.
The dataset is continually streaming, and you need to query the current minimum, maximum, or median at any time.
You need to repeatedly extract extreme values while continuing to insert new ones.

If yes, a Heap is the optimal choice.

Practice Problems

Done	Question	Difficulty
	Kth Largest Element in an Array	Medium
	K Closest Points to Origin	Medium
	Find K Closest Elements	Medium
	Merge K Sorted Lists	Hard
	Median from Data Stream	Hard

Heap / Priority Queue Pattern

The Core Concept: Min Heap Mechanics (Insertion)

Naive Unsorted Array — O(N)O(N)O(N) Extraction

The Binary Heap Breakthrough — O(logN)O(log N)O(logN)

Step-by-Step Traversal

Step 1: Initial Heap

Step 2: Append Element

Step 3: First Sift-Up Comparison

Step 4: Second Sift-Up Comparison

Step 5: Done

Code Implementation

Core Variations

1. Top-K Elements

2. Merge K Sorted Lists

3. Two Heaps (Streaming Median)

When Do I Use This?

Practice Problems

Comments

Naive Unsorted Array — $O(N)$ Extraction

The Binary Heap Breakthrough — $O(log N)$