Who Goes First?
A Priority Queue is a Queue where elements come out based on priority, not arrival time.
- Emergency Room: Heart attack treated before stubbed toe.
- OS Scheduler: High priority processes run first.
1. Hardware Truth: Cache Locality of Heaps
Why are heaps usually arrays even though they are logically trees?
The Comparison
- Tree-based PQ (e.g., AVL/RB-Tree): Every node is a heap-allocated object. To traverse, the CPU must fetch pointers (Pointer Chasing), causing frequent Cache Misses.
- Array-based Heap: All data is stored in a contiguous block of RAM. When the CPU fetches index i, it pre-fetches the surrounding memory (including children at 2i+1, 2i+2) into the L1/L2 Cache.
The Latency Impact
A cache miss to main RAM cost ~100ns. A hit in the L1 cache costs ~1ns. Array-based heaps can be 10-50x faster in practice than tree-based priority queues of the same size.
2. Top K Elements Pattern
Problem: Find the k largest elements in a stream/array.
- Sort: O(N log N).
- Min Heap: O(N log k). Keep a heap of size
k. Ifx > root, pop root, pushx.
3. Interactive: Top K Visualizer
Stream: [10, 5, 20, 3, 40], K = 3.
Goal: Keep 3 largest.
Stream
Min Heap (Size 3)
Start...
4. Implementation
Java
Go
```java
public int findKthLargest(int[] nums, int k) {
PriorityQueue heap = new PriorityQueue<>(); // Min Heap
for (int n : nums) {
heap.offer(n);
if (heap.size() > k) {
heap.poll(); // Remove smallest
}
}
return heap.peek();
}
```
</div>
```go
import "container/heap"
type MinHeap []int
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func findKthLargest(nums []int, k int) int {
h := &MinHeap{}
heap.Init(h)
for _, n := range nums {
heap.Push(h, n)
if h.Len() > k {
heap.Pop(h)
}
}
return (*h)[0]
}
```
</div>
---
## Deep Dive: Kth Largest Element
For a complete breakdown of the Selection Algorithm and a comparison between Heap and Quickselect approaches, visit the Problem Vault:
> [!TIP]
> [**Vault: Kth Largest Element in an Array**](/vault/arrays/kth-largest-element/)
### Practice: Meeting Rooms II
Master the pattern of tracking concurrent events using a Min-Heap:
> [!TIP]
> [**Vault: Meeting Rooms II**](/vault/heaps/meeting-rooms-ii/)
### Practice: K Closest Points to Origin
See how Top K logic applies to 2D coordinates:
> [!TIP]
> [**Vault: K Closest Points to Origin**](/vault/heaps/k-closest-points-to-origin/)
### Hard Practice: Minimum Cost to Hire K Workers
Test your ability to optimize complex constraints using Sorting and Max-Heaps:
> [!TIP]
> [**Vault: Minimum Cost to Hire K Workers**](/vault/heaps/minimum-cost-to-hire-workers/)