Tracing the Array

The priority queue chapter’s trace built a heap with add 5, 8, 3, 1, 4, and 7. The section on finding the next open slot used the same heap. Here it is stored in the array:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 1 │ 3 │ 5 │ 8 │ 4 │ 7 │   size = 6
└───┴───┴───┴───┴───┴───┘

That trace went on with a remove and then add 2. Here they are on the array, one step at a time. Smaller still means higher priority.

remove

remove takes the root out. Copy the last element, at index 5, into index 0, and drop the last slot. Then sink from index 0. Its children are at indices $2 \cdot 0 + 1 = 1$ and $2 \cdot 0 + 2 = 2$ :

  0   1   2   3   4
┌───┬───┬───┬───┬───┐
│ 7 │ 3 │ 5 │ 8 │ 4 │   size = 5
└───┴───┴───┴───┴───┘
  ↑   ↑   ↑
  i left right

The smaller child is 3, and 3 outranks 7, so swap index 0 with index 1. Now i is 1, and its children are at indices $2 \cdot 1 + 1 = 3$ and $2 \cdot 1 + 2 = 4$ :

  0   1   2   3   4
┌───┬───┬───┬───┬───┐
│ 3 │ 7 │ 5 │ 8 │ 4 │   size = 5
└───┴───┴───┴───┴───┘
      ↑       ↑   ↑
      i     left right

The smaller child is 4, and 4 outranks 7, so swap index 1 with index 4. Index 4’s children would be at indices 9 and 10, past the end, so the sink stops:

  0   1   2   3   4
┌───┬───┬───┬───┬───┐
│ 3 │ 4 │ 5 │ 8 │ 7 │   size = 5
└───┴───┴───┴───┴───┘
                  ↑
                  i

add 2

add 2 goes in at index 5, the slot the remove freed. Its parent is at $(5 - 1) /2 = 2$ :

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 3 │ 4 │ 5 │ 8 │ 7 │ 2 │   size = 6
└───┴───┴───┴───┴───┴───┘
          ↑           ↑
       parent         i

2 is smaller than 5, so swap index 5 with index 2. Now i is 2, and its parent is at $(2 - 1) /2 = 0$ , once the remainder is dropped:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 3 │ 4 │ 2 │ 8 │ 7 │ 5 │   size = 6
└───┴───┴───┴───┴───┴───┘
  ↑       ↑
parent    i

2 is smaller than 3, so swap index 2 with index 0. Index 0 is the root, so the swim stops:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 2 │ 4 │ 3 │ 8 │ 7 │ 5 │   size = 6
└───┴───┴───┴───┴───┴───┘
  ↑
  i

These are the same heaps the priority queue chapter’s trace drew after its first remove and after add 2.