Suppose you're writing a scheduler that holds jobs with priorities, where new jobs keep arriving and a worker takes the most urgent waiting job whenever it becomes free. I'd guess most people probably reach for one of two obvious designs first, and I certainly remember doing that myself.
With an unsorted list adding a job costs O(1), although finding the most urgent one means scanning everything (which is O(n)). With a sorted list the most urgent job is already sitting at the front, but every new job has to be inserted in its correct position while the rest get shifted along, and that's O(n) again. So whichever design you choose, I think you'll find one of the two operations always ends up linear in the number of waiting jobs.
Structure Add a job Take the most urgent A million of each Unsorted list O(1) O(n) about 5 × 10¹¹ steps Sorted list O(n) O(1) about 5 × 10¹¹ steps Binary heap O(log n) O(log n) about 4 × 10⁷ steps Half-sorted is enough
A heap keeps just enough order to answer the one question you keep asking, since every parent is guaranteed to be no larger than its children and the minimum therefore always sits at heap[0]. It promises nothing at all about siblings or cousins, and I think this looseness is probably the main reason the updates stay so cheap.
The whole structure also lives in an ordinary array (the children of position i are stored at 2i + 1 and 2i + 2, with its parent at (i − 1) // 2), which means you usually don't have any pointers to look after.
To push a value you place it at the end of the array and keep exchanging it with its parent for as long as it's smaller than that parent. To pop you remove the root and move the last element into its place, and then you keep exchanging that element downwards with its smaller child for as long as it's larger than that child. Every exchange moves one level and a heap holding n items has roughly log₂ n levels, which is where the O(log n) comes from.
Below you can see the array as it goes through pushes of 7, 3, 9, 1 and 5, followed by a pop, another push of 4 and one final pop.
Operation Array afterwards Smallest push 7 [7] 7 push 3 [3, 7] 3 push 9 [3, 7, 9] 3 push 1 [1, 3, 9, 7] 1 push 5 [1, 3, 9, 7, 5] 1 pop, returns 1 [3, 5, 9, 7] 3 push 4 [3, 4, 9, 7, 5] 3 pop, returns 3 [4, 5, 9, 7] 4 You'll probably notice that the array is never actually sorted at any point, because the only guarantee you have concerns the root.
Two patterns that cover most heap questions
The first pattern is keeping k. If you want the k largest of n values you maintain a min-heap of size k. Any new value that beats the root replaces it, so the root is always the k-th largest value you've seen so far. That costs O(n log k) time and O(k) memory, and it still works on a stream that you can't store.
import heapq def kth_largest(nums, k): h = [] for x in nums: if len(h) < k: heapq.heappush(h, x) elif x > h[0]: heapq.heapreplace(h, x) return h[0] kth_largest([3, 2, 1, 5, 6, 4], 2) # 5 The second pattern is taking the best available option. When options appear over time you push each one as it appears and then pop the best one whenever you need to choose. Dijkstra's shortest paths, Huffman coding, merging k sorted lists and most scheduling problems are really this same loop with a different key.
One thing that catches people out in interviews is that looping over a heap's array doesn't give you sorted order. You'd need repeated pops for that, which costs O(n log n) and is exactly what heapsort does.
I originally wrote this up on my site with the pushes and pops animated, in case that's useful: https://academicquant.co.uk/coding-heap-why?utm_source=devto&utm_medium=post&utm_campaign=devto-heap-why