Min-Heaps vs Max-Heaps

Heaps are configured based on whether the application prioritizes minimum values or maximum values.

Min-Heap Mechanics

In a Min-Heap, every parent is smaller than or equal to its children:

Parent ≤ Left Child and Parent ≤ Right Child

Copy codeMin-Heap:
         [ 3 ]
        /     \
     [ 8 ]   [ 5 ]
     /   \
   [ 12 ][ 9 ]

Typical Use Cases:

• Dijkstra’s Algorithm: Greedily extracts the vertex with the shortest path distance.
• Prim’s Minimum Spanning Tree: Picks the edge with the lowest weight.
• K-th Largest Element: Maintain a Min-Heap of size K. The root will hold the K-th largest element!

Max-Heap Mechanics

In a Max-Heap, every parent is greater than or equal to its children:

Parent ≥ Left Child and Parent ≥ Right Child

Copy codeMax-Heap:
         [ 90 ]
        /      \
     [ 50 ]   [ 70 ]
     /    \
   [ 20 ] [ 30 ]

Typical Use Cases:

• Heapsort Algorithm: In-place sorting algorithm that uses a Max-Heap to sort arrays in ascending order in O(n log n) time.
• Operating System CPU Scheduler: Picks the runnable process with the highest priority score.
• Leaderboards: Top-ranking players in mobile games.

PriorityQueue in Kotlin / Java

In the Java and Android SDK, java.util.PriorityQueue is a Min-Heap by default:

Copy codeimport java.util.PriorityQueue

// Default: Min-Heap (smallest number emerges first)
val minHeap = PriorityQueue<Int>()
minHeap.addAll(listOf(50, 10, 30, 5))
println(minHeap.poll()) // Prints: 5

// Configured as Max-Heap via reverseOrder Comparator
val maxHeap = PriorityQueue<Int>(compareByDescending { it })
maxHeap.addAll(listOf(50, 10, 30, 5))
println(maxHeap.poll()) // Prints: 50

Summary

• Min-Heaps keep the smallest element at the root; Max-Heaps keep the largest element at the root.
• In Java/Kotlin, PriorityQueue defaults to a Min-Heap; pass compareByDescending to convert it into a Max-Heap.