Heaps/priority queues might seem scary at first, but once you understand how they work and how to apply them, they are the easiest problem to get during your interview. Here are some tips to identify and solve any priority queue problem.

Let’s first clarify the difference between Priority Queues and Heaps. In short: Priority Queue is an idea of a queue-like data type where elements are served by priority not insertion order, and Heaps are a concrete implementation of a data structure that is most commonly used as a Priority Queue. There are other possible implementations of Priority Queues such as Red-Black Trees. In practice, the two terms are often used interchangeably.

When to Use Heaps: The Key Indicator

One of the biggest giveaways that heaps are needed is when the problem involves dynamic or streaming data. Heaps allow you to process incoming data as it arrives and provide the ability to query for the maximum or minimum value at any time. When the data is static, it is often sufficient to use a sorting algorithm. However, for dynamic datasets where elements are continually added or removed, heaps offer efficient O(log n) insertion and deletion operations, making them ideal for maintaining order in real-time.

Common Problem Patterns Involving Heaps

1. Kth Largest/Smallest Element

Scenario: If the problem asks for the Kth largest or smallest element in a collection, heaps are ideal since they allow efficient insertion and extraction of the minimum or maximum element.

Example: "Find the Kth largest number in a stream."

Approach:

• Dynamic Data: Since the data may be continuously updated, a heap allows you to maintain the K largest elements efficiently.
• Implementation: Use a min-heap of size k to keep track of the top k largest elements in real-time.

LeetCode Example: 703. Kth Largest Element in a Stream

2. Merging or Sorting Multiple Lists

Scenario: Problems that require merging multiple sorted lists or arrays can often be optimized using a heap. This allows you to keep track of the smallest (or largest) element from each list and merge efficiently.

Example: "Merge k sorted linked lists into one sorted list."

Approach:

• Dynamic Selection: A heap helps you dynamically select the next smallest element among the heads of the lists.
• Implementation: Use a min-heap to store the current smallest element from each list.

LeetCode Example: 23. Merge k Sorted Lists

3. Frequent Elements

Scenario: If you're asked to find the top K most frequent elements or similar problems involving frequency and ranking, heaps can be used to efficiently maintain the top K elements as you process the data.

Example: "Find the top K most frequent words in a list of words."

Approach:

• Dynamic Counting: While the data may be static, heaps allow for efficient retrieval of the top frequencies without sorting the entire frequency map.
• Implementation: Use a min-heap of size k to keep track of the top K elements based on frequency.

LeetCode Example: 692. Top K Frequent Words

4. Dynamic Minimum/Maximum

Scenario: Any problem where you need to repeatedly access the minimum or maximum element in a dynamic dataset (inserting and removing elements) is a strong indicator for using a heap.

Example: "Design a data structure that supports inserting numbers and retrieving the maximum number at any time."

Approach:

• Dynamic Data: As elements are added or removed, the heap maintains the ordering.
• Implementation: Use a max-heap to maintain the maximum element.

LeetCode Example: 716. Max Stack

5. Scheduling or Task Execution

Scenario: If the problem involves scheduling tasks based on priorities or deadlines, a priority queue can help efficiently pick the next task to execute based on priority.

Example: "Given tasks with deadlines and durations, find the optimal schedule to maximize completed tasks."

Approach:

• Dynamic Selection: Tasks may be added or priorities may change; a heap allows for efficient retrieval of the highest priority task.
• Implementation: Use a heap to select the next task based on priority criteria (e.g., earliest deadline).

LeetCode Example: 621. Task Scheduler

6. Sliding Window Problems

Scenario: Problems where you need to track the maximum or minimum value in a sliding window (e.g., "find the maximum in each sliding window of size K") often benefit from heaps to efficiently maintain the range's top elements.

Example: "Find the maximum number in each sliding window of size K in an array."

Approach:

• Dynamic Window: As the window slides, elements enter and exit the window dynamically.
• Implementation: Use a max-heap to keep track of the maximum element in the current window, taking care to discard elements that are no longer in the window.

LeetCode Example: 239. Sliding Window Maximum

7. Shortest Path or Minimum Spanning Tree

Scenario: Graph-related problems like Dijkstra’s algorithm (for shortest paths) or Prim’s algorithm (for minimum spanning trees) make heavy use of priority queues to efficiently find the next node with the smallest cost.

Example: "Find the shortest path from a source node to all other nodes in a weighted graph."

Approach:

• Dynamic Edge Weights: The priority queue (min-heap) allows for efficient selection of the next node with the smallest tentative distance.
• Implementation: Use a min-heap to store nodes with their current shortest distance estimates.

LeetCode Example: 743. Network Delay Time

8. Order Statistics

Scenario: When the problem requires maintaining some sort of running order statistic, such as finding the median in a dynamic stream of numbers.

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

Approach:

• Dynamic Median: As new numbers come in, the median can change.
• Implementation: Use two heaps—a max-heap for the lower half and a min-heap for the upper half—to maintain balance and efficiently compute the median.

LeetCode Example: 295. Find Median from Data Stream

_____________________

That's pretty much it!

I have more tips, examples and a step-by-step guide on heaps in my blog: https://blog.faangshui.com/p/my-heaps-dont-lie

Let's connect on LinkedIn: https://www.linkedin.com/in/nurbolat/