Heaps and Priority Queues

Introduction

Heaps and priority queues are powerful data structures that efficiently maintain ordered collections where you frequently need to access the minimum or maximum element. From finding top K elements to implementing Dijkstra’s algorithm, these structures are essential tools in every programmer’s toolkit.

In this comprehensive guide, we’ll explore classic heap and priority queue problems with clean, optimized solutions in both C# and Python.

What is a Heap?

A heap is a specialized tree-based data structure that satisfies the heap property:

Min Heap: Parent node is always smaller than or equal to its children (root is minimum)
Max Heap: Parent node is always greater than or equal to its children (root is maximum)

Key Operations

• Insert: Add element while maintaining heap property – O(log n)
• Extract Min/Max: Remove and return root element – O(log n)
• Peek: View root element without removing – O(1)
• Heapify: Convert array into heap – O(n)

Common Use Cases

• Finding top K elements efficiently
• Priority-based task scheduling
• Graph algorithms (Dijkstra’s, Prim’s)
• Median maintenance in streaming data
• Merge K sorted lists

Problem 1: Kth Largest Element in a Stream

Difficulty: Easy
Tags: Heap, Design, Priority Queue

Problem Statement

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in sorted order, not the kth distinct element.

Implement KthLargest class:

• KthLargest(int k, int[] nums): Initializes the object with integer k and stream of integers nums
• int add(int val): Appends integer val to the stream and returns the kth largest element

Example

Input:
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]

Output:

[null, 4, 5, 5, 8, 8]

Approach: Min Heap of Size K

The key insight is to maintain a min heap of exactly K elements. The root of this heap will always be the kth largest element because:

• The heap contains the K largest elements seen so far
• The smallest of these K elements is the kth largest overall

C# Solution

public class KthLargest 
{
    private PriorityQueue<int, int> minHeap;
    private int k;
    
    public KthLargest(int k, int[] nums) 
    {
        this.k = k;
        this.minHeap = new PriorityQueue<int, int>();
        
        // Add all initial numbers
        foreach (int num in nums) 
        {
            Add(num);
        }
    }
    
    public int Add(int val) 
    {
        // Add new value to heap
        minHeap.Enqueue(val, val);
        
        // Keep only k largest elements
        if (minHeap.Count > k) 
        {
            minHeap.Dequeue();
        }
        
        // The root is the kth largest
        return minHeap.Peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.Add(val);
 */

Python Solution

import heapq

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.heap = nums
        
        # Transform list into a heap in O(n) time
        heapq.heapify(self.heap)
        
        # Keep only k largest elements
        while len(self.heap) > k:
            heapq.heappop(self.heap)
    
    def add(self, val: int) -> int:
        heapq.heappush(self.heap, val)
        
        # Maintain heap size of k
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        
        # Root is the kth largest element
        return self.heap[0]

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

Time Complexity:

• Constructor: O(n log k) where n is length of nums
• Add: O(log k)

Space Complexity: O(k)

Key Insights

• Min heap keeps K largest elements, smallest at root
• When heap exceeds K elements, remove the minimum
• The kth largest is always at the root of our min heap
• Much more efficient than sorting after each addition

Problem 2: Top K Frequent Elements

Difficulty: Medium
Tags: Heap, Hash Table, Sorting

Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Input: nums = [1], k = 1
Output: [1]

Approach: Hash Map + Heap

1. Count frequencies using a hash map
2. Use a heap to find k elements with highest frequencies

C# Solution

public class Solution 
{
    public int[] TopKFrequent(int[] nums, int k) 
    {
        // Count frequencies
        Dictionary<int, int> frequencyMap = new Dictionary<int, int>();
        foreach (int num in nums) 
        {
            if (frequencyMap.ContainsKey(num)) 
            {
                frequencyMap[num]++;
            } 
            else 
            {
                frequencyMap[num] = 1;
            }
        }
        
        // Use max heap based on frequency
        PriorityQueue<int, int> maxHeap = new PriorityQueue<int, int>(
            Comparer<int>.Create((a, b) => b.CompareTo(a))
        );
        
        foreach (var pair in frequencyMap) 
        {
            maxHeap.Enqueue(pair.Key, pair.Value);
        }
        
        // Extract top k elements
        int[] result = new int[k];
        for (int i = 0; i < k; i++) 
        {
            result[i] = maxHeap.Dequeue();
        }
        
        return result;
    }
}

Python Solution

from collections import Counter
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Count frequencies
        frequency_map = Counter(nums)
        
        # Use heapq.nlargest to find k elements with highest frequencies
        # key function specifies we're comparing by frequency
        return heapq.nlargest(k, frequency_map.keys(), 
                             key=lambda x: frequency_map[x])

Time Complexity: O(n + m log k) where n is array length, m is unique elements
Space Complexity: O(m) for the frequency map

Alternative Approach: Bucket Sort

For O(n) time complexity when k is close to number of unique elements:

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        frequency_map = Counter(nums)
        
        # Create buckets where index = frequency
        buckets = [[] for _ in range(len(nums) + 1)]
        for num, freq in frequency_map.items():
            buckets[freq].append(num)
        
        # Collect k most frequent elements
        result = []
        for i in range(len(buckets) - 1, -1, -1):
            result.extend(buckets[i])
            if len(result) >= k:
                return result[:k]
        
        return result

Problem 3: Find K Pairs with Smallest Sums

Difficulty: Medium
Tags: Heap, Array, Two Pointers

Problem Statement

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u, v) which consists of one element from the first array and one element from the second array.

Return the k pairs with the smallest sums.

Example

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are:
[1,2], sum = 3
[1,4], sum = 5
[1,6], sum = 7

Approach: Min Heap with Smart Generation

Instead of generating all pairs (which could be huge), use a min heap to generate pairs on-demand, starting with the smallest possible sums.

C# Solution

public class Solution 
{
    public IList<IList<int>> KSmallestPairs(int[] nums1, int[] nums2, int k) 
    {
        var result = new List<IList<int>>();
        if (nums1.Length == 0 || nums2.Length == 0 || k == 0) 
            return result;
        
        // Min heap: (sum, index1, index2)
        var minHeap = new PriorityQueue<(int i, int j), int>();
        
        // Initialize heap with pairs using first element of nums2
        for (int i = 0; i < Math.Min(k, nums1.Length); i++) 
        {
            minHeap.Enqueue((i, 0), nums1[i] + nums2[0]);
        }
        
        // Extract k smallest pairs
        while (k > 0 && minHeap.Count > 0) 
        {
            var (i, j) = minHeap.Dequeue();
            result.Add(new List<int> { nums1[i], nums2[j] });
            
            // Add next pair from nums2 for this nums1 element
            if (j + 1 < nums2.Length) 
            {
                minHeap.Enqueue((i, j + 1), nums1[i] + nums2[j + 1]);
            }
            
            k--;
        }
        
        return result;
    }
}

Python Solution

import heapq

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], 
                       k: int) -> List[List[int]]:
        if not nums1 or not nums2:
            return []
        
        # Min heap: (sum, index1, index2)
        min_heap = []
        
        # Initialize with pairs using first element of nums2
        for i in range(min(k, len(nums1))):
            heapq.heappush(min_heap, (nums1[i] + nums2[0], i, 0))
        
        result = []
        
        # Extract k smallest pairs
        while k > 0 and min_heap:
            sum_val, i, j = heapq.heappop(min_heap)
            result.append([nums1[i], nums2[j]])
            
            # Add next pair from nums2 for this nums1 element
            if j + 1 < len(nums2):
                heapq.heappush(min_heap, 
                              (nums1[i] + nums2[j + 1], i, j + 1))
            
            k -= 1
        
        return result

Time Complexity: O(k log k)
Space Complexity: O(k)

Key Insights

• Don’t generate all possible pairs (could be O(n²))
• Start with smallest possible pairs and expand systematically
• Each extracted pair suggests only one new candidate pair
• Leverages the sorted property of input arrays

Key Takeaways

Heap Patterns

1. Top K Elements: Use heap of size K for efficient tracking
2. K-way Merge: Use heap to merge multiple sorted sequences
3. Running Median: Use two heaps (max heap + min heap)
4. Frequency-based: Combine hash map with heap

Choosing Heap Type

• Min Heap for K largest: Keep K largest, remove smallest
• Max Heap for K smallest: Keep K smallest, remove largest
• Both heaps: For median or balanced partitioning

Best Practices

• Consider heap when you need repeated min/max operations
• Heapify is O(n), faster than n insertions for initialization
• Python’s heapq only provides min heap (negate values for max heap)
• C#’s PriorityQueue allows custom comparers
• Always check if heap is empty before peek/pop

When to Use Heaps

Perfect for:

• Finding top/bottom K elements
• Maintaining a running minimum/maximum
• Priority-based processing
• K-way merge operations

Not ideal for:

• When you need to search for arbitrary elements
• Sorted traversal of all elements
• When insert/delete frequency is low

Practice Problems

Ready to master heaps? Try these:

1. Merge K Sorted Lists – Classic K-way merge
2. Find Median from Data Stream – Two heap technique
3. Sliding Window Median – Advanced heap management
4. Meeting Rooms II – Interval scheduling with heap
5. Reorganize String – Greedy with max heap

Conclusion

Heaps and priority queues are indispensable for efficiently solving problems involving ordered data and top K queries. Understanding when to use min vs max heaps, and how to combine them with other data structures like hash maps, will significantly expand your problem-solving capabilities.

The key is recognizing patterns: when you need repeated access to minimum/maximum elements, think heap!

What’s Next? In our next article, we’ll explore trees and binary search trees, building on our understanding of heap structures.

Happy coding! 🚀

Have questions or suggestions? Drop a comment below!