Heaps and Priority Queues
A binary heap keeps the smallest item at the root using an array and a simple shape rule, so insert and extract both cost log n. It gives a sort that meets the comparison bound and, more usefully, a queue ordered by importance rather than by arrival.
What a learner can do afterwards
- Insert into a heap and restore the heap property by sifting up
- Extract the minimum and restore the property by sifting down
- Say why a heap is stored in an array with no pointers at all
1 · Read
A priority queue hands you the most important item first, not the oldest one. You can build one from a sorted list, where inserts shift things and removal is instant, or from a binary heap, which keeps both operations cheap.
A heap needs no pointers because its shape is fixed: every level is full except possibly the last, which fills left to right. So the tree lives in a plain array with the root at index 0 and the children of index i at 2i+1 and 2i+2.
A value rule keeps the smallest item at the root: every parent is no larger than its children. Insert appends the new item at the end and sifts up, swapping with its parent until the rule holds. Extract removes the root, moves the last item to the root, then sifts down, swapping with the smaller child until the rule holds.
Each fix walks one root to leaf path, so insert and extract each cost log n. Extracting the minimum again and again sorts in n log n, which meets the comparison bound, and schedulers use the same step to answer what is most urgent right now.
A heap stores a fixed shape tree in an array and sifts along one path, so the smallest item is always ready in log n time.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.