Heaps and priority queues

A heap maintains partial order: the minimum or maximum is easy to remove, while the whole structure is not sorted. Priority queues are the interface; heaps are a common implementation. They are useful for top-k, scheduling, merge-k-lists, and shortest-path algorithms.

Trade-off: compare time, memory, and implementation complexity before committing to a structure or pattern.

On interviews: Expect questions about push/pop complexity, why sorting all values is wasteful for top-k, and why Dijkstra needs priority by current distance.

Common pitfalls: JavaScript has no built-in heap, so describe the data structure or use a small implementation. Remember that peeking is O(1), but insert and remove are O(log n).

Checklist:

• Distinguish heap from sorted array.
• Use top-k when k is small.
• Name O(log n) updates.
• Clarify min-heap or max-heap.