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.
More to read
Practice Exercises: Trees and Priority Queues
Practice: Trees, Queues, and Heaps
Binary search trees keep elements in ascending sorted order, but they can become unbalanced. In the worst case, a binary search tree can end up looking exactly like a linked list. Try this: find an order for inserting 7, 3, 8, 1, 2, 5, 6, 4 into a binary search tree so the result looks like a linked list.
Now think about the priority queue abstract data type. A priority queue hands you the most important item first, not the oldest one. There are two common ways to build one:
1. Keep a sorted list. Every insert has to shift elements around so the list stays in order, but taking the smallest item is instant. 2. Use a binary heap. A heap needs no pointers at all because its shape is fixed: every level is full except possibly the last, which fills left to right, so the tree can live 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 again. 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. Repeatedly extracting the minimum sorts in n log n, meeting the comparison bound, and schedulers use the same operation to answer 'what is most urgent right now' without keeping everything sorted.
2 · Watch
En anglaisTake it off screen
Where it sits
Optional connections
This opens up
Nothing builds on it yet.
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.