Last time, I used a hypothetical work assignment to introduce the concept of a priority queue. Let’s continue with that for a little longer.
You had been working at your new job for a few hours when your friend the computer programmer came by. Seeing you struggling, he asked you to describe what you were doing. He thought for a minute and then proposed a new solution. Rather than laying the cubes out in a line, he suggested that you build a pyramid, like this:
03
04 05
11 23 37 41
50All he did was take the sorted list and turn it into a pyramid with the smallest cube at the top and the other cubes filling the levels from left to right, in order. Then, he gave you some simple rules to ensure that, when you remove or insert a cube, the smallest cube ends up at the top.
Here are the rules for removing the smallest cube.
- Pull the item from the top of the pyramid. That leaves you an empty space, represented by XX.
XX
04 05
11 23 37 41
50 - Take the last item in the pyramid (the right-most cube on the lowest level) and place it in the top spot, giving you:
50
04 05
11 23 37 41 - While the cube is larger than the smallest of the two cubes directly below it (its children), swap the item with its smallest child. Stop if the item moves to the bottom level (the leaf level) because it has no children. In this case, 50 is larger than 4, so we swap.
04
50 05
11 23 37 4150 is still larger than its children, so we need to swap again, resulting in this.
04
11 05
50 23 37 41And we’re done because the node is now at the leaf level.
If you always follow those rules, the smallest item will always end up on the top. For example, if you removed the smallest now, you’d get this progression:
41 Move 41 to the top spot
11 05
50 23 37
--------------
05 Swap 41 with 05
11 41
50 23 37
--------------
05 Swap 41 with 37
11 37
50 23 41That takes care of removing an item. What about adding an item? That has some simple rules, too.
- Add the item to the first empty spot in the structure. That is, the lowest, leftmost unoccupied position. Let’s say we want to add a cube with the number 3 to the structure directly above, resulting in:
05
11 37
50 23 41 03 - While the item is smaller than its parent (the cube above it), swap the item with its parent. Obviously we’ll stop if the item gets to the top, because the root has no parent. In this case, 03 is smaller than 37, so we end up with:
05
11 03
50 23 41 3703 is smaller than 05 (its new parent), so we swap again, leaving us with:
03
11 05
50 23 41 37
To add a cube with number 38, you’d add it to the structure below and to the left of 50. 38 is less than 50, so you’d swap the two cubes and you’d be left with:
03
11 05
38 23 41 37
50If you always follow those rules for adding and removing, the smallest cube will always be on the top and you will always be able to do quick additions and removals.
That structure looks like it’s in crazy order, I know. But if you play with it a little more, adding and removing items, you’ll find that it really does work. It would take you maybe an hour of practice in applying the rules before you’re ripping right along, easily keeping up with the people coming by to drop cubes on your counter or to get the smallest one. It’s a lot faster.
When you remove a cube you take the last cube from the structure, place it at the top, and sift it down. It should be obvious that you can’t sift down more levels than there are in the structure. So sifting the cube down will never take more operations than there are occupied levels. In that first example there were three levels after we moved 50 to the top spot, so it couldn’t have required more than three swaps to move the cube into its final position.
Adding an item is similar. When you add a cube, you bubble it up. You can’t bubble up more levels than there are in the structure, so adding an item will never require more operations than there are occupied levels.
So the number of levels is the deciding factor. If there are n levels, it will never take more than n swaps to add or remove an item.
With each level containing twice as many cubes as the previous level, it takes very little effort to work with a fairly large number of cubes. This table shows how many items fit into a structure of a given height.
| Levels | Total cubes |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| 7 | 127 |
| 8 | 255 |
| 9 | 511 |
| 10 | 1023 |
You still need lots of horizontal space, but only half as much as you would with a sorted list. The last level of a 10-level structure would contain 512 cubes. Still, this type of structure wouldn’t be bad at all for working with, say, 100 cubes. Your bottom row would only have 64 items.
The really nice thing, though, is that with 100 items you never have to make more than seven moves to insert or remove an item. That’s a far cry from the 100 moves you’d have to make if you were to insert something at the head of a sorted list containing 100 items.
What I have described above is a binary heap; a very useful, efficient, and easy to implement type of priority queue. Although slower than a sorted list when removing items, it’s hugely faster on insertion, more than making up the difference. Considering that you can’t remove more than you insert, it turns out that the “expensive” removal of binary heap is more than offset by the very inexpensive (in comparison to a sorted list) insertion.
I’ve found that too many textbooks and programming tutorials make binary heaps look a lot harder than they are. You can see from the description of the process above that they are very simple, requiring just a few rules that a child can master after maybe an hour of practice. As you’ll see in my next post, it’s almost that easy to represent a binary heap in code. Stay tuned.