Heap and Priority Queue Guide

What Is a Heap?

A complete binary tree where parent is always ≥ children (max-heap) or ≤ children (min-heap). Insert and extract-min/max in O(log n). Often implemented as a priority queue.

Top-K Problems

• K largest: Min-heap of size K; if current element larger than heap top, pop and push.
• K smallest: Max-heap of size K (or min-heap with negated values in languages that don't have max-heap).
• K closest points: Min-heap by distance, pop K times (or max-heap of size K).

Merge K Sorted Lists

Push the head of each list into a min-heap. Pop the smallest, add its next to the heap. Repeat. Time O(N log K) where N is total nodes.

Other Uses

• Find median: two heaps (max-heap for lower half, min-heap for upper half).
• Task scheduler: max-heap by frequency, schedule most frequent first (with cooldown).

Language Notes

• JavaScript: no built-in heap; use array and manual bubble up/down or a library.
• Python: heapq is a min-heap; negate for max-heap.

Summary

"K largest/smallest" or "merge K sorted" → think heap. Practice on Preplume(/).