TwiddleLab / Code / Data Structures You Can See

Heaps and Priority Queues

Lesson 8 of 10 · 7 min · Free, no account needed

What you will learn

• A priority queue hands out the most urgent item first, not the oldest.
• A heap does it with a tree where every parent is at least as urgent as its children, so the top is always the most urgent.
• Insert: add at the end, swap up while it beats its parent. Take: the last item jumps to the top and swaps down. A few swaps, one path.
• The tree lives in a plain list: parent of i is (i - 1) // 2, children are 2i + 1 and 2i + 2.

Start the lesson

How the lesson goes

1. In a game, events are waiting. Which happens next?

   Not the oldest: the most urgent. Lower number = more urgent. Tap the next one, three times.

2. A pile where the most urgent floats to the top.

   Every parent must be more urgent than its children. A new event joins at the bottom: swap it up as far as it should go.

   After a swap, the old parent sits under the new node, which beats it, and it already beat its other child. So the rule holds everywhere except maybe between the new node and its new parent. Check that one, and repeat.

3. The tree is secretly a list.

   Read the tree row by row, left to right, and you get the list underneath. Find nodes in the list.

4. A heap, used as a priority queue.

   A priority queue always hands out the most urgent item next. A heap is the usual way to build one.

   Heap rule: every parent is at least as urgent as its children. So the top, index 0, is the most urgent.

   It's stored in a list: parent of i is (i - 1) // 2, children are 2i + 1 and 2i + 2. Insert swaps up, take swaps down.

5. Serve the most urgent event.

   The top leaves. The last item jumps into its place. Swap it down until the rule holds again.

6. Event storm.

   Events arrive and get served, mixed up. Keep the heap a heap. Few misses wins stars.

7. Write the bubble-up.

   1 was just added at the end of the heap. Move it up while it beats its parent.

8. How a game AI finds a path: A*.

   A* keeps the cells it might explore in a heap and always takes the best one. Be the heap: pick the cell it explores next.

9. Your code builds a heap.

   Seven events arrive. Your bubble-up from earlier puts each one in place.

Previous lesson: Binary Search Trees · Next lesson: Choosing the Right Structure · Part of the course: Data Structures You Can See

Lessons are interactive and need JavaScript. Turn it on to play them.