Mastering Heaps & Priority Queues

If you’ve ever struggled with problems that need constant access to the largest or smallest item — like “get the top K elements”, “find the median”, or “schedule tasks by priority” — you’re going to love this:

What’s a Priority Queue?

A priority queue is like a normal queue, but smarter — elements are served based on priority (not just arrival time).

In Java, PriorityQueue is the go-to class — and it’s powered by a heap under the hood.

What’s a Heap?

A heap is a binary tree stored as an array, optimised for:

1. Always keeping the min (or max) element on top.
2. Efficient Operations -
3. Insert → O(log n)
4. Remove min/max → O(log n)
5. Peek min/max → O(1)

Java makes this easy:

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        

When Should You Use It?

Some popular examples where Priority Queues are used -

• Top K frequent elements
• Smash the two heaviest stones
• Median from data stream
• Dijkstra’s shortest path
• Task schedulers, job queues, network packet prioritisation

Let’s Code One Example Together

📌 LeetCode 1046: Last Stone Weight - Smash the two heaviest stones together until one (or none) remains.

• We want to find a solution that makes both removing the maximums, and adding a new stone, less than O(N).
• For this kind of maximum-maintenance, we use a Max-Heap
• Note that a Max-Heap is a data structure that can take items, and can remove and return the maximum, with both operations taking O(logN) time. It does this by maintaining the items in a special order (within the array), or as a balanced binary tree.
• While most programming languages have a Heap/ Priority Queue data structure, some, such as Python and Java, only have Min-Heap.
• Just as the name suggests, this is a Heap that instead of always returning the maximum item, it returns the minimum.
• There are two ways to convert this Min-Heap to a Max-Heap:
• Multiply all numbers going into the heap by -1, and then multiply them by -1 to restore them when they come out.
• Or, Pass a comparator in (language-dependent).
• Here, I will use the second way in Java

Time Complexity - O(n log n)

Space Complexity - O(n)

Simple, clean, powerful.

🎯 Takeaway

Heaps let you think less about sorting and more about solving. They show up in interviews more often than you’d think.

If you’re preparing for interviews or trying to solve problems smarter — master heaps. You won’t regret it.

💬 Used heaps recently? Got a favourite heap-based problem? Share below 👇

#Java #DSA #LeetCode #InterviewPrep #PriorityQueue #Heaps #CodingTips #SoftwareEngineering