A binary heap is a complete binary tree (stored compactly in an array) with the heap property: in a min-heap every parent is smaller than its children, so the minimum sits at the root. Insert and extract-min are O(log n); peeking the minimum is O(1).
Fast access to the extreme
A heap doesn't keep everything sorted — it just guarantees the smallest (min-heap) or largest (max-heap) is always at the top. That is exactly what 'repeatedly take the best' problems need.
k-th largest with a min-heap of size k
heap = empty min-heap
for x in array:
push(heap, x)
if size(heap) > k: pop(heap) // drop the smallest
return top(heap) // the k-th largestO(n log k)→O(k)
Each of n pushes/pops on a size-k heap is O(log k).
⚡ The edge
- When you need the smallest or largest repeatedly, or the top k, a heap gives O(log n) per operation — far cheaper than re-sorting (O(n log n)) when k is small.
- A size-k heap solves 'k-th largest' in O(n log k) and O(k) space — better than sorting the whole array.
Worked example
Find the 2nd largest of [3, 1, 5, 2] using a min-heap of size 2.
- Push 3, push 1 -> heap holds {1, 3}; size is 2.
- Push 5 -> {1, 3, 5}, size 3 > 2, pop the smallest (1) -> {3, 5}. Push 2 -> size 3, pop 2 -> {3, 5}.
- The heap's top (smallest of the two largest) is 3 — the 2nd largest.
Answer: 2nd largest = 3
Worked example
Why is building a heap from n elements O(n), not O(n log n)?
- Inserting one by one would be O(n log n), but heapify works bottom-up.
- Most nodes are near the leaves and sift down only a little; the work forms a converging series.
- Summed over all nodes, the total is O(n).
Answer: Bottom-up heapify is O(n)
⚠ Watch out
- A heap is not fully sorted — only the root is guaranteed to be the extreme.
- Finding or deleting an arbitrary (non-top) element is O(n), not O(log n).
- Use a min-heap for 'k largest' and a max-heap for 'k smallest' — it feels backwards but keeps the heap small.