Applications: Scheduling, Leaderboards, Caching

Priority Queues and Heaps power some of the most critical systems in operating systems and backend services.

1. Operating System Event Timers & AlarmManager

When an Android app sets alarms or scheduled jobs:

Copy codealarmManager.setExact(AlarmManager.RTC_WAKEUP, triggerAtMillis, pendingIntent)

The Android OS kernel manages thousands of scheduled wakeups from hundreds of apps. How does the kernel know which alarm to fire next?

The Solution: Min-Heap of Timestamps

• Root of the Min-Heap holds the earliest upcoming alarm in O(1).
• When the timer fires, the OS wakes up the device, extracts the root in O(log n), and sets the hardware timer interrupt for the new root!

2. Top-K Elements Problem

The Problem

Given a stream of 100,000,000 search queries, find the Top 10 most frequent queries in real time without sorting the entire dataset.

The Min-Heap Approach:

1. Maintain a Min-Heap of size 10.
2. For each query frequency:
   • If heap has < 10 elements, insert it.
   • If heap has 10 elements and current frequency > heap.peek():
     • Pop the smallest element and insert the new one.
3. Total time: O(N log K) instead of O(N log N)!
4. Memory: only O(K) space instead of holding all N items in memory.

Copy codefun topKFrequent(nums: IntArray, k: Int): IntArray {
    val frequencyMap = nums.toList().groupingBy { it }.eachCount()
    // Min-heap ordered by frequency count
    val minHeap = PriorityQueue<Int>(compareBy { frequencyMap[it] })

    for (num in frequencyMap.keys) {
        minHeap.add(num)
        if (minHeap.size > k) {
            minHeap.poll() // Remove smallest frequency
        }
    }
    return minHeap.toIntArray()
}

3. Data Compression: Huffman Coding

Huffman coding is the foundational entropy encoding algorithm used in ZIP, JPEG, and MP3:

• Builds an optimal prefix code tree by repeatedly merging the two lowest-frequency characters using a Min-Heap.

Summary