Heap and priority queue

Overview

A heap is a complete binary tree that satisfies heap order. A priority queue uses it to always expose the highest or lowest priority element quickly.

Problems to practice

• Kth largest element
• Top K frequent elements
• Merge K sorted lists
• Find median in a stream
• Smallest number in a range with priority

Time and space complexity

• Insert: O(log n)
• Extract min/max: O(log n)
• Peek: O(1)

Example interview answer

“I would use a min-heap because we need the smallest k candidates constantly. This keeps the heap size bounded and gives efficient insertion and removal.”