Algorithmic Strategies for Heaps

Introduction

Heaps are specialized tree-based data structures that satisfy the heap property: in a max heap, each parent node is greater than or equal to its children; in a min heap, each parent is less than or equal to its children. The key to solving heap problems efficiently is recognizing when you need quick access to minimum or maximum elements and applying the right heap strategy. This guide explores the most common strategies with real C# implementations from LeetCode problems.

Common Algorithmic Strategies

When approaching heap problems, you’ll typically encounter one of these strategies:

• Min Heap: Efficiently access and remove the minimum element
• Max Heap: Efficiently access and remove the maximum element
• Two Heaps: Maintain two heaps for median or balanced partitioning
• Priority Queue: Process elements by priority rather than insertion order
• Top K Elements: Find k largest/smallest elements efficiently
• Heap Sort: Sort using heap data structure
• Brute Force: Sort entire array or use simple data structures

Strategy 1: Min Heap

A Min Heap is a complete binary tree where each parent node is less than or equal to its children, making the minimum element always at the root. In C#, we typically use SortedSet<T> or PriorityQueue<TElement, TPriority> (.NET 6+) to simulate min heap behavior. Min heaps provide O(log n) insertion and removal, with O(1) access to the minimum element. They’re ideal for algorithms that repeatedly need the smallest element.

When to use it

• Need frequent access to minimum element
• Process elements in ascending order
• Find k largest elements (keep k smallest in heap)
• Merge k sorted lists/arrays
• Dijkstra’s shortest path algorithm

Time Complexity: O(log n) for insert/remove | Space Complexity: O(n)

Problem: Kth Largest Element (Using Min Heap)

Find the kth largest element by maintaining a min heap of size k.

Implementation:

public class Solution
{
    public int FindKthLargest(int[] nums, int k)
    {
        // Min heap of size k keeps k largest elements
        var minHeap = new SortedSet<(int val, int index)>();

        for (int i = 0; i < nums.Length; i++)
        {
            minHeap.Add((nums[i], i));
            
            if (minHeap.Count > k)
            {
                minHeap.Remove(minHeap.Min);
            }
        }

        return minHeap.Min.val;
    }
}

Key Insight: Keep a min heap of size k. The root of this heap is the kth largest element. When heap size exceeds k, remove the smallest element.

Problem: Merge K Sorted Lists

Merge k sorted linked lists using a min heap.

Implementation:

public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

public class Solution
{
    public ListNode MergeKLists(ListNode[] lists)
    {
        if (lists == null || lists.Length == 0)
            return null;

        var minHeap = new SortedSet<(int val, int listIndex, ListNode node)>();

        // Initialize heap with first node from each list
        for (int i = 0; i < lists.Length; i++)
        {
            if (lists[i] != null)
            {
                minHeap.Add((lists[i].val, i, lists[i]));
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        while (minHeap.Count > 0)
        {
            var (val, listIndex, node) = minHeap.Min;
            minHeap.Remove(minHeap.Min);

            current.next = node;
            current = current.next;

            if (node.next != null)
            {
                minHeap.Add((node.next.val, listIndex, node.next));
            }
        }

        return dummy.next;
    }
}

Key Insight: Keep the smallest element from each list in the min heap. Always take the minimum, add to result, and insert the next element from that list.

Strategy 2: Max Heap

A Max Heap is a complete binary tree where each parent node is greater than or equal to its children, keeping the maximum element at the root. In C#, we simulate max heaps using SortedSet<T> with reverse comparison or PriorityQueue with negated priorities. Max heaps provide O(log n) insertion and removal with O(1) access to the maximum element. They’re perfect for problems requiring frequent access to the largest element.

When to use it

• Need frequent access to maximum element
• Process elements in descending order
• Find k smallest elements (keep k largest in heap)
• Scheduling problems (highest priority first)
• Stream of numbers - track maximum

Time Complexity: O(log n) for insert/remove | Space Complexity: O(n)

Problem: Top K Frequent Elements

Find k most frequent elements in an array.

Implementation:

public class Solution
{
    public int[] TopKFrequent(int[] nums, int k)
    {
        if (nums.Length == k) return nums;
        var cnt = new Dictionary<int, int>();

        foreach (int n in nums)
        {
            if (cnt.ContainsKey(n)) cnt[n]++;
            else cnt.Add(n, 1);
        }

        List<int> ans = new List<int>();

        if (cnt.Count == k)
        {
            foreach (var item in cnt) ans.Add(item.Key);
            return ans.ToArray();
        }

        var cmp = Comparer<int>.Create((a, b) => cnt[a] != cnt[b] ? cnt[a].CompareTo(cnt[b]) : a.CompareTo(b));
        var ss = new SortedSet<int>(cmp);

        foreach (var item in cnt)
        {
            ss.Add(item.Key);
            if (ss.Count > k) ss.Remove(ss.Min);
        }
        while (ss.Count > 0)
        {
            ans.Add(ss.Min);
            ss.Remove(ss.Min);
        }

        ans.Reverse();
        return ans.ToArray();
    }
}

Key Insight: Use a frequency map, then maintain a min heap of size k based on frequency. Elements in the heap are the k most frequent.

Problem: Last Stone Weight

Simulate smashing the two heaviest stones together repeatedly.

Implementation:

public class Solution
{
    public int LastStoneWeight(int[] stones)
    {
        var maxHeap = new SortedSet<(int weight, int index)>(
            Comparer<(int, int)>.Create((a, b) => 
            {
                int cmp = b.weight.CompareTo(a.weight);
                return cmp != 0 ? cmp : a.index.CompareTo(b.index);
            })
        );

        for (int i = 0; i < stones.Length; i++)
        {
            maxHeap.Add((stones[i], i));
        }

        int index = stones.Length;

        while (maxHeap.Count > 1)
        {
            var heaviest1 = maxHeap.Max;
            maxHeap.Remove(heaviest1);
            
            var heaviest2 = maxHeap.Max;
            maxHeap.Remove(heaviest2);

            if (heaviest1.weight != heaviest2.weight)
            {
                int newWeight = heaviest1.weight - heaviest2.weight;
                maxHeap.Add((newWeight, index++));
            }
        }

        return maxHeap.Count == 0 ? 0 : maxHeap.Max.weight;
    }
}

Key Insight: Max heap keeps heaviest stones accessible. Remove two heaviest, add difference back if not equal, repeat until one or zero stones remain.

Strategy 3: Two Heaps

Two Heaps is a powerful technique that uses both a min heap and a max heap simultaneously to maintain a balanced partition of data. The classic use case is finding the median of a stream: the max heap stores the smaller half of numbers, the min heap stores the larger half. By keeping heaps balanced (sizes differ by at most 1), the median is always at the top of one or both heaps. This pattern extends to any problem requiring efficient access to middle elements or balanced partitioning.

When to use it

• Find median in a data stream
• Sliding window median
• Maintain balanced partitions of data
• Need access to both ends of middle section
• Problems requiring “middle” element tracking

Time Complexity: O(log n) for insert | Space Complexity: O(n)

Problem: Find Median from Data Stream

Design a data structure that supports adding numbers and finding the median.

Implementation:

public class MedianFinder
{
    private SortedSet<(int num, int index)> sm = new SortedSet<(int num, int index)>();
    private SortedSet<(int num, int index)> gt = new SortedSet<(int num, int index)>();
    private int index = 0;

    public MedianFinder() { }

    public void AddNum(int num)
    {
        if (gt.Count > 0 && num > gt.Min.num)
        {
            gt.Add((num, index++));
            if (gt.Count > sm.Count)
            {
                sm.Add(gt.Min);
                gt.Remove(gt.Min);
            }
        }
        else
        {
            sm.Add((num, index++));
            if (sm.Count > gt.Count + 1)
            {
                gt.Add(sm.Max);
                sm.Remove(sm.Max);
            }
        }
    }

    public double FindMedian()
    {
        return sm.Count > gt.Count ? sm.Max.num : (sm.Max.num + gt.Min.num) / 2.0;
    }
}

Key Insight: Max heap (sm) stores smaller half, min heap (gt) stores larger half. Keep heaps balanced. If odd count, max heap has one extra element.

Detailed Explanation:

• Max Heap (smaller half): Contains the smaller 50% of numbers, maximum is at top
• Min Heap (larger half): Contains the larger 50% of numbers, minimum is at top
• Balance invariant: Max heap size equals min heap size, or max heap has one extra element
• Median access: If heaps equal size, median is average of both tops; otherwise, it’s the max heap’s top

Problem: Sliding Window Median

Find median in each sliding window of size k.

Implementation:

public class Solution
{
    public double[] MedianSlidingWindow(int[] nums, int k)
    {
        List<double> result = new List<double>();
        List<int> window = new List<int>();

        for (int i = 0; i < nums.Length; i++)
        {
            window.Add(nums[i]);

            if (window.Count == k)
            {
                var sorted = window.OrderBy(x => x).ToList();
                double median;
                
                if (k % 2 == 0)
                {
                    median = ((long)sorted[k / 2 - 1] + (long)sorted[k / 2]) / 2.0;
                }
                else
                {
                    median = sorted[k / 2];
                }

                result.Add(median);
                window.RemoveAt(0);
            }
        }

        return result.ToArray();
    }
}

Key Insight: For sliding window, maintain two heaps and handle additions/removals carefully. Simpler approach sorts each window (less efficient but clearer).

Optimized with Two Heaps Pattern:

// Use two heaps and lazy deletion for O(n log k) solution
// Track elements to remove in separate set
// Rebalance heaps after each window slide

Strategy 4: Priority Queue

A Priority Queue is an abstract data type where elements are served based on their priority rather than insertion order. Higher priority elements are dequeued first. In C#, use PriorityQueue<TElement, TPriority> (.NET 6+) or simulate with SortedSet<T>. Priority queues are essential for algorithms like Dijkstra’s, task scheduling, and any scenario where you need to process items by importance or value rather than FIFO order.

When to use it

• Task scheduling by priority
• Event-driven simulation
• Dijkstra’s shortest path
• A* search algorithm
• Merge intervals by start time
• Process items by custom ordering

Time Complexity: O(log n) for enqueue/dequeue | Space Complexity: O(n)

Problem: Design Twitter

Design a simplified Twitter with posting tweets and news feed functionality.

Implementation:

public class Twitter
{
    private class Tweet
    {
        public int TweetId { get; set; }
        public int Timestamp { get; set; }
    }

    private Dictionary<int, List<Tweet>> tweets;
    private Dictionary<int, HashSet<int>> following;
    private int timestamp;

    public Twitter()
    {
        tweets = new Dictionary<int, List<Tweet>>();
        following = new Dictionary<int, HashSet<int>>();
        timestamp = 0;
    }

    public void PostTweet(int userId, int tweetId)
    {
        if (!tweets.ContainsKey(userId))
            tweets[userId] = new List<Tweet>();

        tweets[userId].Add(new Tweet 
        { 
            TweetId = tweetId, 
            Timestamp = timestamp++ 
        });
    }

    public IList<int> GetNewsFeed(int userId)
    {
        var feed = new SortedSet<(int timestamp, int tweetId)>(
            Comparer<(int, int)>.Create((a, b) =>
            {
                int cmp = b.Item1.CompareTo(a.Item1);
                return cmp != 0 ? cmp : b.Item2.CompareTo(a.Item2);
            })
        );

        // Add user's own tweets
        if (tweets.ContainsKey(userId))
        {
            foreach (var tweet in tweets[userId])
            {
                feed.Add((tweet.Timestamp, tweet.TweetId));
                if (feed.Count > 10) feed.Remove(feed.Min);
            }
        }

        // Add followed users' tweets
        if (following.ContainsKey(userId))
        {
            foreach (var followeeId in following[userId])
            {
                if (tweets.ContainsKey(followeeId))
                {
                    foreach (var tweet in tweets[followeeId])
                    {
                        feed.Add((tweet.Timestamp, tweet.TweetId));
                        if (feed.Count > 10) feed.Remove(feed.Min);
                    }
                }
            }
        }

        return feed.Select(x => x.tweetId).ToList();
    }

    public void Follow(int followerId, int followeeId)
    {
        if (followerId == followeeId) return;
        
        if (!following.ContainsKey(followerId))
            following[followerId] = new HashSet<int>();
        
        following[followerId].Add(followeeId);
    }

    public void Unfollow(int followerId, int followeeId)
    {
        if (following.ContainsKey(followerId))
            following[followerId].Remove(followeeId);
    }
}

Key Insight: Use priority queue (sorted by timestamp) to merge tweets from user and all followed users. Keep only top 10 most recent tweets.

Problem: Task Scheduler

Schedule tasks with cooldown period to minimize total time.

Implementation:

public class Solution
{
    public int LeastInterval(char[] tasks, int n)
    {
        // Count frequency of each task
        int[] freq = new int[26];
        foreach (char task in tasks)
        {
            freq[task - 'A']++;
        }

        // Sort frequencies in descending order
        Array.Sort(freq);
        Array.Reverse(freq);

        // Max frequency task determines minimum time
        int maxFreq = freq[0];
        int idleSlots = (maxFreq - 1) * n;

        // Fill idle slots with other tasks
        for (int i = 1; i < 26 && freq[i] > 0; i++)
        {
            idleSlots -= Math.Min(freq[i], maxFreq - 1);
        }

        // If idle slots remain, add them; otherwise, all tasks fit
        return idleSlots > 0 ? idleSlots + tasks.Length : tasks.Length;
    }
}

Key Insight: Most frequent task creates a schedule pattern. Fill idle slots between repetitions with other tasks. If slots remain empty, those become actual idle time.

Strategy 5: Top K Elements

The Top K Elements pattern uses heaps to efficiently find the k largest or smallest elements from a collection. The counter-intuitive trick: use a min heap of size k to find k largest elements (or max heap for k smallest). This works because maintaining exactly k elements in the heap and removing the minimum/maximum ensures only the k largest/smallest remain. This approach is more space-efficient than sorting the entire array.

When to use it

• Find k largest/smallest elements
• Top k frequent elements
• K closest points to origin
• Kth largest element in stream
• Limited memory for large datasets

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

Problem: K Closest Points to Origin

Find k closest points to the origin (0, 0).

Implementation:

public class Solution
{
    public int[][] KClosest(int[][] points, int k)
    {
        // Max heap of size k (by distance)
        var maxHeap = new SortedSet<(int dist, int index)>(
            Comparer<(int, int)>.Create((a, b) =>
            {
                int cmp = b.dist.CompareTo(a.dist);
                return cmp != 0 ? cmp : b.index.CompareTo(a.index);
            })
        );

        for (int i = 0; i < points.Length; i++)
        {
            int dist = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            maxHeap.Add((dist, i));

            if (maxHeap.Count > k)
            {
                maxHeap.Remove(maxHeap.Max);
            }
        }

        int[][] result = new int[k][];
        int idx = 0;
        
        foreach (var (dist, index) in maxHeap)
        {
            result[idx++] = points[index];
        }

        return result;
    }
}

Key Insight: Use max heap of size k. As we iterate, keep only k closest points by removing the farthest point when heap exceeds size k.

Problem: Kth Largest Element in a Stream

Design a class to find the kth largest element in a stream.

Implementation:

public class KthLargest
{
    private SortedSet<(int val, int index)> minHeap;
    private int k;
    private int index;

    public KthLargest(int k, int[] nums)
    {
        this.k = k;
        this.index = 0;
        this.minHeap = new SortedSet<(int val, int index)>();

        foreach (int num in nums)
        {
            Add(num);
        }
    }

    public int Add(int val)
    {
        minHeap.Add((val, index++));

        if (minHeap.Count > k)
        {
            minHeap.Remove(minHeap.Min);
        }

        return minHeap.Min.val;
    }
}

Key Insight: Maintain a min heap of size k containing the k largest elements seen so far. The root is always the kth largest element.

Strategy 6: Heap Sort

Heap Sort is a comparison-based sorting algorithm that uses a heap data structure. It works by building a max heap from the input, then repeatedly extracting the maximum element and placing it at the end of the array. While not as commonly used as quicksort or mergesort in practice (due to cache performance), heap sort guarantees O(n log n) time complexity and O(1) space complexity, making it useful for memory-constrained environments.

When to use it

• Need guaranteed O(n log n) time
• Space complexity must be O(1)
• In-place sorting required
• Understanding heap operations
• Teaching/learning purposes

Time Complexity: O(n log n) | Space Complexity: O(1)

Implementation:

public class Solution
{
    public void HeapSort(int[] arr)
    {
        int n = arr.Length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--)
        {
            Heapify(arr, n, i);
        }

        // Extract elements from heap one by one
        for (int i = n - 1; i > 0; i--)
        {
            // Move current root to end
            Swap(arr, 0, i);

            // Heapify reduced heap
            Heapify(arr, i, 0);
        }
    }

    private void Heapify(int[] arr, int n, int i)
    {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest])
            largest = left;

        if (right < n && arr[right] > arr[largest])
            largest = right;

        if (largest != i)
        {
            Swap(arr, i, largest);
            Heapify(arr, n, largest);
        }
    }

    private void Swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Key Insight: Build max heap, then repeatedly swap root (maximum) with last element and heapify the reduced heap.

Strategy 7: Brute Force

Brute Force approaches for heap-related problems typically involve sorting the entire array or using simpler data structures like arrays or lists with linear search. While these solutions have worse time complexity (O(n log n) for sorting, O(n) for linear operations), they’re straightforward to implement and understand. They serve as good baselines before optimizing with heaps.

When to use it

• Problem size is small (n < 100)
• Simplicity preferred over efficiency
• Quick prototype needed
• Establishing correctness
• Heap implementation not available

Time Complexity: O(n log n) to O(n²) | Space Complexity: O(n)

Example: Top K Elements by Sorting

public class Solution
{
    public int[] TopKFrequentBruteForce(int[] nums, int k)
    {
        // Count frequencies
        var freq = new Dictionary<int, int>();
        foreach (int num in nums)
        {
            freq[num] = freq.GetValueOrDefault(num, 0) + 1;
        }

        // Sort by frequency (O(n log n))
        var sorted = freq.OrderByDescending(x => x.Value)
                        .Select(x => x.Key)
                        .Take(k)
                        .ToArray();

        return sorted;
    }
}

Key Insight: Sort by frequency and take top k. Simple but O(n log n) time instead of O(n log k) with heap.

Example: Median Without Heaps

public class MedianFinderBruteForce
{
    private List<int> numbers;

    public MedianFinderBruteForce()
    {
        numbers = new List<int>();
    }

    public void AddNum(int num)
    {
        numbers.Add(num);
    }

    public double FindMedian()
    {
        numbers.Sort(); // O(n log n) every time!
        int n = numbers.Count;
        
        if (n % 2 == 0)
            return (numbers[n / 2 - 1] + numbers[n / 2]) / 2.0;
        else
            return numbers[n / 2];
    }
}

Key Insight: Sort entire list for every median query. Simple but inefficient - O(n log n) per query instead of O(log n) with two heaps.

Strategy Selection Guide

Problem Type	Strategy	Time	Space
Find kth largest	Min Heap (size k)	O(n log k)	O(k)
Find kth smallest	Max Heap (size k)	O(n log k)	O(k)
Top k frequent	Min Heap with frequency	O(n log k)	O(n)
Median in stream	Two Heaps	O(log n) insert	O(n)
Merge k sorted lists	Min Heap	O(n log k)	O(k)
Task scheduling	Priority Queue	O(n log n)	O(n)
K closest points	Max Heap (size k)	O(n log k)	O(k)
Sort array	Heap Sort	O(n log n)	O(1)

Pattern Recognition Tips

1. “K largest/smallest”? → Think Min/Max Heap of size k
2. “Median” or “middle”? → Think Two Heaps
3. “Merge k sorted”? → Think Min Heap
4. “Priority” or “schedule”? → Think Priority Queue
5. “Top k frequent”? → Think Heap with frequency
6. “Stream of numbers”? → Think Heap-based data structure
7. “Repeatedly access min/max”? → Think Heap, not sorting

Common Pitfalls

1. Using wrong heap type: Min heap for k largest (not max heap!)
2. Not handling duplicates: Use index as tiebreaker in SortedSet
3. Rebalancing two heaps: Ensure size difference is at most 1
4. .NET heap limitations: SortedSet isn’t a true heap (slower for some operations)
5. Integer overflow: Use long for distance calculations
6. Memory vs speed: Heaps trade space for time efficiency

Advanced Techniques

Lazy Deletion in Two Heaps

// Track elements to remove
HashSet<int> toRemove = new HashSet<int>();

// Don't remove immediately, mark as deleted
void LazyRemove(int val)
{
    toRemove.Add(val);
}

// Clean up when accessing top
void CleanTop(SortedSet<(int, int)> heap)
{
    while (heap.Count > 0 && toRemove.Contains(heap.Min.Item1))
    {
        toRemove.Remove(heap.Min.Item1);
        heap.Remove(heap.Min);
    }
}

Custom Comparer for Complex Objects

var heap = new SortedSet<MyObject>(
    Comparer<MyObject>.Create((a, b) =>
    {
        // Primary comparison
        int cmp = a.Priority.CompareTo(b.Priority);
        if (cmp != 0) return cmp;
        
        // Tiebreaker
        return a.Id.CompareTo(b.Id);
    })
);

Conclusion

Mastering heap strategies is essential for solving optimization and priority-based problems efficiently. The key is to:

1. Identify the pattern - Is it about k elements, median, or priority?
2. Choose the right heap type - Min for k largest, max for k smallest, two for median
3. Consider space-time tradeoffs - Heaps use O(k) or O(n) space for O(log k) or O(log n) operations
4. Handle edge cases - Empty heaps, single elements, k = n
5. Understand C# limitations - SortedSet vs PriorityQueue, need for index tiebreakers

Practice these strategies on LeetCode to build intuition for when heaps provide optimal solutions. With time, you’ll recognize heap patterns instantly and leverage their power for efficient problem-solving! 🚀

References

LeetCode. (2024). Heap Problems. https://leetcode.com/tag/heap-priority-queue/

Cormen, T. H., Leiserson, C. E., Rivert, R. L. & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

Williams, J. W. J. (1964). Algorithm 232: Heapsort. Communications of the ACM.