Min Heap vs Max Heap: The Intuition That Finally Clicks

If you’ve ever been confused about when to use a min-heap vs max-heap, you’re not alone.

At first glance, it feels simple:

• Min-heap → gives smallest
• Max-heap → gives largest

But then interview problems like Top K Frequent Elements or K Closest Points completely mess with that intuition.

Let’s fix that — properly.

The Real Difference (Not What You Think)

The difference is not just about smallest vs largest.

It’s about the role the heap plays in your solution:

1. Min-Heap → Filtering (Removing the weakest)

2. Max-Heap → Selection (Picking the strongest)

The Mental Model That Works

Min-Heap → “Kick out the weakest”

You are maintaining a limited set (usually size K).

You remove the least useful element repeatedly.

👉 Think: Who should be removed next?

Max-Heap → “Pick the strongest”

You want the best element at every step.

👉 Think: Who should be used next?

5 Tricky Problems (With Intuition + Kotlin)

1. Top K Frequent Elements

❌ Trap

Max-heap of all elements

✅ Correct

Min-heap of size K (filter weakest frequencies)

Key intuition

We maintain:

best K frequent elements seen so far

When heap exceeds K:

remove least frequent element

Why we never remove a valid Top K element

When heap size becomes K+1:

• the smallest frequency is removed
• but there already exist K elements inside heap that are ≥ it

So:

it is impossible for the removed element to belong to final Top K

Because if K elements are already better, it is disqualified.

Kotlin Solution

import java.util.PriorityQueue
fun topKFrequent(nums: IntArray, k: Int): IntArray {
    val freq = HashMap<Int, Int>()
    for (n in nums) freq[n] = freq.getOrDefault(n, 0) + 1
    val heap = PriorityQueue<Pair<Int, Int>> { a, b ->
        a.second - b.second // min-heap by frequency
    }
    for ((num, count) in freq) {
        heap.offer(Pair(num, count))
        if (heap.size > k) heap.poll()
    }
    val result = IntArray(k)
    var i = 0
    while (heap.isNotEmpty()) {
        result[i++] = heap.poll().first
    }
    return result
}

2. Kth Largest Element

❌ Trap

Max heap of all elements

✅ Correct

Min heap of size K

Intuition

We keep only K largest elements.

Root becomes:

Kth largest

Kotlin Solution

import java.util.PriorityQueue
fun findKthLargest(nums: IntArray, k: Int): Int {
    val heap = PriorityQueue<Int>() // min heap
    for (n in nums) {
        heap.offer(n)
        if (heap.size > k) heap.poll()
    }
    return heap.peek()
}

3. Merge K Sorted Lists

❌ Trap

Get Neeraja Gandla’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Thinking in Top K terms

✅ Correct

Min heap of current list heads

Intuition

Heap stores:

next smallest candidate from each list

We always:

• pick smallest
• move pointer forward
• insert next node

Kotlin Solution

import java.util.PriorityQueue
class ListNode(var `val`: Int) {
    var next: ListNode? = null
}
fun mergeKLists(lists: Array<ListNode?>): ListNode? {
    val heap = PriorityQueue<ListNode> { a, b ->
        a.`val` - b.`val`
    }
    for (node in lists) {
        if (node != null) heap.offer(node)
    }
    val dummy = ListNode(0)
    var curr = dummy
    while (heap.isNotEmpty()) {
        val node = heap.poll()
        curr.next = node
        curr = curr.next!!
        node.next?.let { heap.offer(it) }
    }
    return dummy.next
}

4. Reorganize String

❌ Trap

Min heap

✅ Correct

Max heap with cooldown (previous character blocking)

Intuition

• always pick most frequent character
• but cannot reuse immediately
• so we temporarily hold previous character

Kotlin Solution

import java.util.PriorityQueue
fun reorganizeString(s: String): String {
    val freq = HashMap<Char, Int>()
    for (c in s) freq[c] = freq.getOrDefault(c, 0) + 1
    val heap = PriorityQueue<Pair<Char, Int>> { a, b ->
        b.second - a.second // max heap
    }
    for ((ch, count) in freq) {
        heap.offer(Pair(ch, count))
    }
    val result = StringBuilder()
    var prev: Pair<Char, Int>? = null
    while (heap.isNotEmpty()) {
        val curr = heap.poll()
        result.append(curr.first)
        val updated = Pair(curr.first, curr.second - 1)
        if (prev != null && prev.second > 0) {
            heap.offer(prev)
        }
        prev = updated
    }
    return if (prev != null && prev.second > 0) "" else result.toString()
}

5. K Closest Points to Origin

❌ Trap

Min heap of all points

✅ Correct

Max heap of size K (remove farthest)

Intuition

We maintain:

K closest points seen so far

Root:

farthest among selected K

Kotlin Solution

import java.util.PriorityQueue
fun kClosest(points: Array<IntArray>, k: Int): Array<IntArray> {
    val heap = PriorityQueue<Pair<Int, IntArray>> { a, b ->
        b.first - a.first // max heap by distance
    }
    for (p in points) {
        val dist = p[0] * p[0] + p[1] * p[1]
        heap.offer(Pair(dist, p))
        if (heap.size > k) heap.poll()
    }
    val result = Array(k) { IntArray(2) }
    var i = 0
    while (heap.isNotEmpty()) {
        result[i++] = heap.poll().second
    }
    return result
}

The Ultimate Decision Table

The Interview Cheat Code

Ask yourself:

“What should the heap prioritize at the top?”

• weakest → Min-Heap
• strongest → Max-Heap
• bounded best K → Min-Heap
• greedy best choice → Max-Heap

Final One-Liner

If I maintain K elements → Min-Heap
If I repeatedly pick best → Max-Heap

Closing Thought

Heap problems are not about data structures.

They are about invariants:

What am I trying to preserve at every step?

Once you see that, all heap problems become variations of the same idea.