Heap Data Structures: Min & Max Heaps, Priority Queues, and Top-K Problem Patterns

A Heap is a specialized tree-based data structure that satisfies the complete binary tree property alongside a strict heap ordering property. By maintaining either a minimum or maximum value at the root node, heaps enable $O(1)$ time access to extreme values and $O(\log N)$ time for insertions and deletions. This makes heaps the foundational engine behind priority queues, real-time job schedulers, dynamic stream processing algorithms, and top-$K$ element filtering patterns.

1. Fundamental Mental Model: Complete Binary Trees & Heap Properties

To qualify as a heap, a binary tree must strictly satisfy two fundamental criteria: the Shape Property and the Order Property.

         Complete Binary Tree (Valid Heap Shape)
                           (Root)
                            /  \
                          (L)  (R)
                          / \  /
                        (L)(R)(L)

The Shape Property

A heap must be a Complete Binary Tree (CBT):

• Every tree level must be completely filled with nodes, except possibly the bottom-most level.
• If the last level is incomplete, all nodes on that level must be filled sequentially from left to right without any gaps.

The Order Property

The relative values between parent nodes and child nodes determine the heap type:

• Min-Heap: The value of every parent node is less than or equal to the values of its children ($P \le C$). Consequently, the global minimum element always resides at the root node.
• Max-Heap: The value of every parent node is greater than or equal to the values of its children ($P \ge C$). Consequently, the global maximum element always resides at the root node.

Conceptually: Unlike a Binary Search Tree (BST), a heap does not maintain a strict left-to-right sorting across the entire tree. It only guarantees a local vertical hierarchy between parents and children.

2. Array-Based Tree Representation & Index Formulae

Because a heap is a complete binary tree without empty structural gaps, it can be efficiently represented as a contiguous 0-indexed flat array without storing explicit node pointers (left, right).

Array Representation:  [ 1,  3,  6,  5,  9,  8 ]
Index Position:          0   1   2   3   4   5

Mathematical Index Mapping

For any node positioned at index $i$ in a 0-indexed array:

Index Verification Example

Given the array [1, 3, 6, 5, 9, 8]:

• Root Node ($i = 0$, Value = 1):
  • Left Child Index: $2(0) + 1 = 1 \rightarrow \text{Value } 3$
  • Right Child Index: $2(0) + 2 = 2 \rightarrow \text{Value } 6$
• Node at Index $i = 1$ (Value = 3):
  • Left Child Index: $2(1) + 1 = 3 \rightarrow \text{Value } 5$
  • Right Child Index: $2(1) + 2 = 4 \rightarrow \text{Value } 9$
• Parent Calculation for Index $i = 3$ (Value = 5):
  • Parent Index: $\lfloor \frac{3 - 1}{2} \rfloor = 1 \rightarrow \text{Value } 3$

3. Heap Rebalancing Mechanics: Heapify Up & Heapify Down

When inserting or removing elements, the shape or ordering property of the heap can be temporarily violated. The Heapify operation restores heap invariants in $O(\log N)$ time.

Heapify Up (Shift Up / Bubble Up)

Used during insertion (offer / add). When a new element is appended to the bottom-leftmost available array slot, it bubbles upward until it reaches a valid position relative to its parent.

Code Snippet: Custom Heapify Up Implementation

private void heapifyUp(int index) {
    while (index > 0) {
        int parentIndex = (index - 1) / 2;
        // Min-Heap Condition: If child is smaller than parent, swap
        if (heap.get(index) < heap.get(parentIndex)) {
            swap(index, parentIndex);
            index = parentIndex; // Move up to parent's position
        } else {
            break; // Heap property restored
        }
    }
}

Heapify Down (Shift Down / Bubble Down)

Used during deletion or extraction of the root (poll / remove). The root element is replaced by the last array element, which then sinks downward by swapping with the smaller child (in a Min-Heap) until order is restored.

Code Snippet: Custom Heapify Down Implementation

private void heapifyDown(int index) {
    int size = heap.size();
    while (index < size) {
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;
        int smallest = index;

        if (leftChild < size && heap.get(leftChild) < heap.get(smallest)) {
            smallest = leftChild;
        }
        if (rightChild < size && heap.get(rightChild) < heap.get(smallest)) {
            smallest = rightChild;
        }

        if (smallest != index) {
            swap(index, smallest);
            index = smallest; // Move down to child's position
        } else {
            break; // Heap property restored
        }
    }
}

4. Core Operations & Time Complexity Analysis

The depth of a complete binary tree containing $N$ elements is bounded by $\lfloor \log_2 N \rfloor$. Because heap restoration paths travel exclusively vertically down or up single tree branches, operations execute within logarithmic upper bounds.

5. Java Implementation: PriorityQueue Paradigm & Custom Comparators

In standard libraries (such as Java's java.util.PriorityQueue), heaps underpin priority queue implementations.

Instantiation Strategies

import java.util.PriorityQueue;
import java.util.Collections;

// 1. Default Min-Heap (Natural Ascending Order)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 2. Default Max-Heap (Reverse Order Comparator)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// 3. Custom Lambda Comparator (Min-Heap based on custom metric)
PriorityQueue<int[]> customMinHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));

Custom Comparator Logic Mechanics

Java comparators adhere to standard integer sign conventions:

• Returning a negative value ($< 0$) indicates the first argument (a) has higher priority and should move closer to the root.
• Returning a positive value ($> 0$) indicates the second argument (b) has higher priority.
• Returning zero ($0$) indicates equal priority.

// Ascending Order Comparator Logic (Min-Heap)
PriorityQueue<Integer> customMin = new PriorityQueue<>((a, b) -> {
    return Integer.compare(a, b); // a < b returns -1 -> 'a' prioritized
});

// Descending Order Comparator Logic (Max-Heap)
PriorityQueue<Integer> customMax = new PriorityQueue<>((a, b) -> {
    return Integer.compare(b, a); // b > a returns +1 -> 'b' prioritized
});

6. Problem Pattern 1: Top K Frequent Elements

Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements.

Optimal Heap Strategy (Min-Heap of Size $K$)

1. Frequency Mapping: Compute node occurrences using a Hash Map in $O(N)$ time.
2. Bounded Heap Processing: Maintain a Min-Heap of capacity $K$ storing unique elements, prioritized by their frequency values.
3. Window Maintenance: For each key in the map:
   • Insert key into the Min-Heap.
   • If heap size exceeds $K$, perform poll(). This automatically purges the element with the lowest frequency among all elements evaluated so far.
4. Extraction: The remaining $K$ keys inside the heap represent the top $K$ frequent elements.

Code Implementation

import java.util.*;

public class TopKFrequentElements {
    public int[] topKFrequent(int[] nums, int k) {
        // Step 1: Build frequency map
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // Step 2: Min-Heap prioritizing key frequency
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(
            (a, b) -> Integer.compare(frequencyMap.get(a), frequencyMap.get(b))
        );

        // Step 3: Maintain heap window of size K
        for (int key : frequencyMap.keySet()) {
            minHeap.offer(key);
            if (minHeap.size() > k) {
                minHeap.poll(); // Evict element with lowest frequency
            }
        }

        // Step 4: Extract results from heap
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = minHeap.poll();
        }

        return result;
    }
}

Complexity Analysis

• Time Complexity: $O(N \log K)$. Populating the map takes $O(N)$. Inserting unique elements into a heap bounded by size $K$ takes $O(\log K)$ per key, yielding $O(U \log K)$ where $U \le N$.
• Space Complexity: $O(N + K)$ auxiliary memory for Hash Map and Heap storage.

7. Problem Pattern 2: Kth Smallest Element in a Sorted Matrix

Problem Statement

Given an $N \times N$ matrix where each of the rows and columns is sorted in ascending order, find the $K$-th smallest element in the matrix.

Optimal Heap Strategy (Max-Heap Boundary Control)

To isolate the $K$-th smallest element across an un-flattened 2D grid:

1. Initialize a Max-Heap bounded to size $K$.
2. Traverse all elements in the $N \times N$ matrix.
3. Push each element into the Max-Heap.
4. If the heap size exceeds $K$, immediately perform poll(). This drops the current maximum value within the active collection.
5. After scanning the grid, the Max-Heap holds the $K$ absolute smallest values from the matrix, with the $K$-th smallest sitting at the top (peek()).

Code Implementation

import java.util.PriorityQueue;
import java.util.Collections;

public class KthSmallestInMatrix {
    public int kthSmallest(int[][] matrix, int k) {
        // Step 1: Instantiate Max-Heap using reverse order
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        int n = matrix.length;

        // Step 2: Iterate through 2D grid
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                maxHeap.offer(matrix[i][j]);

                // Maintain fixed heap window of size K
                if (maxHeap.size() > k) {
                    maxHeap.poll(); // Evict largest element among current K+1 candidates
                }
            }
        }

        // Step 3: Top of Max-Heap contains K-th smallest element
        return maxHeap.peek();
    }
}

Complexity Analysis

• Time Complexity: $O(N^2 \log K)$. Iterating over $N \times N$ matrix cells takes $N^2$ steps, with heap operations bounded by $O(\log K)$.
• Space Complexity: $O(K)$ auxiliary memory to maintain the heap instance.

8. Primary Real-World Applications & Algorithmic Use Cases

1. Continuous Stream Median Calculation:
   • Uses two heaps simultaneously: a Max-Heap to store the lower half of values and a Min-Heap for the upper half.
   • Keeps half-sizes balanced within a delta of $1$ to yield $O(1)$ access to stream medians.
2. Dijkstra’s Single-Source Shortest Path Algorithm:
   • Utilizes a Min-Heap priority queue to track unvisited nodes ordered by distance.
   • Allows extracting the next closest node in $O(\log V)$ time instead of scanning arrays in $O(V)$.
3. Merge $K$ Sorted Lists:
   • Uses a Min-Heap of size $K$ storing current head pointers of sorted arrays/lists.
   • Efficiently pulls global minimums in $O(N \log K)$ overall runtime.
4. Operating System Task Schedulers:
   • Prioritizes CPU execution threads dynamically based on variable urgency levels rather than simple FIFO queues.

9. Comparative Analysis of Heap Variants & Patterns

10. Summary and Key Takeaways

• Complete Binary Tree Invariant: A heap must be filled across all upper levels completely, with nodes at the bottom level added strictly left-to-right.
• Array Mapping Mechanics: Nodes stored in a 0-indexed array map directly to children via $2i + 1$ (left) and $2i + 2$ (right), with parents located at $\lfloor (i-1)/2 \rfloor$.
• Logarithmic Bounds: Both heapifyUp (for insertions) and heapifyDown (for deletions) operate within $O(\log N)$ time by traversing tree heights vertically.
• Top-K Reverse Intuition: To find the Top $K$ largest elements, utilize a Min-Heap of size $K$; to find the Top $K$ smallest elements, utilize a Max-Heap of size $K$.
• Dynamic Window Maintenance: Enforcing heap.size() > k inside processing loops bounds auxiliary memory usage to $O(K)$ and reduces time complexity to $O(N \log K)$.
• Comparator Mechanics: Custom Java PriorityQueue behavior relies on Integer.compare(), where returning negative integers prioritizes the first element over the second.