How to make a Heap work

This will be a worked example. I'm not writing up the class notes again.

This is the map that will be used for this example. We will be getting from A to B, as tradition demands. Records on the heap will consist of two items of data: a letter representing the name of a city, and a number, representing the earliest time we know for certain that we could get there if we departed from A at time 0 and took the best route. When the algorithm starts, the only thing we now is that we could get to A at time 0, so the heap just has that one thing in it:
1: A at 0
2:
3:
4:
5:
6:
7:
8:      
9:      
10:      
11:      
12:      
13:      
14:      
15:      
Remember that although heaps are usually implemented inside arrays, it makes the caluclations a lot cleaner to assume that the first position is at position 1. That also allows an index of 0 to be used to indicate "not present".

This is the algorithm. Repeatedly...
  1. Remove the city with the earliest ETA from the heap: (C0=the city, T0=its ETA).
  2. For every road i leading out of C0:
    1. Find its length Ri, and the city Ci at the other end of it.
    2. Compute the time Ti=T0+Ri that we could reach Ci by following road i.
    3. If Ci has never been in the heap, add it with Ti as its priority.
    4. If Ci Already has a lower ETA than Ti, do nothing.
    5. If Ci is already in the heap, but with an ETA higher than Ti, change its ETA to Ti and adjust its position in the heap if necessary.
  3. Stop when the heap is empty

So let's do it

  1. "A at 0" is removed from the heap. C0=A, T0=0, and the heap is empty.
    Time=0, Location=A
  2. There are three roads leading from A: length 2 leading to F, length 4 leading to E, and length 5 leading to D. None of F, E, or D have been in the heap before, so three new entries are added: "F at 2", "E at 4", and "D at 5". The heap now looks like this.
    1: F at 2
    2: E at 4
    3: D at 5
    4:
    5:
    6:
    7:
    8:      
    9:      
    10:      
    11:      
    12:      
    13:      
    14:      
    15:      
  3. Round the loop again. "F at 2" is removed from the heap
    Time=2, Location=F
    C0=F, T0=2, and the heap is repaired to look like this.
    1: E at 4
    2: D at 5
    3:
    4:
    5:
    6:
    7:
    8:      
    9:      
    10:      
    11:      
    12:      
    13:      
    14:      
    15:      
  4. Three roads lead from F. Following each of them would lead to A at 2+2=4, N at 2+9=11, and M at 2+8=10. A has already been on the heap with an ETA of 0, so the new 4 is ignored. N and M are new to the heap, so they are added, giving:
    1: E at 4
    2: D at 5
    3: N at 11
    4: M at 10
    5:
    6:
    7:
    8:      
    9:      
    10:      
    11:      
    12:      
    13:      
    14:      
    15:      
  5. Round the loop again. "E at 4" is removed, C0=E, T0=4, and the heap looks like this.
    Time=4, Location=E
    1: D at 5
    2: N at 11
    3: M at 10
    4:
    5:
    6:
    7:
    8:      
    9:      
    10:      
    11:      
    12:      
    13:      
    14:      
    15:      
  6. Three roads lead from E; following each of them (remember the time is now 4) would lead to D at 4+6=10, A at 4+4=8, and M at 4+7=11. D is already on the heap with an ETA of 5, so the new value of 10 is ignored. A has already been on the heap with an ETA of 0, so the new 8 is ignored. M is already on the heap with an ETA of 10, so the new 11 is ignored. Overall result of this step: nothing happens. E isn't on the shortest path from A to anywhere.
  7. Round the loop again. "D at 5" is removed, and the heap looks like this.
    Time=5, Location=D
    1: M at 10
    2: N at 11
    3:
    4:
    5:
    6:
    7:
    8:      
    9:      
    10:      
    11:      
    12:      
    13:      
    14:      
    15:      
  8. The time is now 5, C0=D, T0=5. Four roads lead from D. Following them would yield the following events: "A at 10" (ignored), "E at 11" (ignored), "X at 22" (added), and "N at 8". N is already on the heap, but it's old ETA of 11 has just been improved upon. So the overall effect of this step is that N gets promoted to 8 and X gets added at 22.
    1: N at 8
    2: M at 10
    3: X at 22
    4:
    5:
    6:
    7:
    8:      
    9:      
    10:      
    11:      
    12:      
    13:      
    14:      
    15:      
  9. Round the loop again, "N at 8" is removed, C0=N, the time now, T0 is 8.
    Time=8, Location=N
    1: M at 10
    2: X at 22
    3:
    4:
    5:
    6:
    7:
    8:      
    9:      
    10:      
    11:      
    12:      
    13:      
    14:      
    15:      
  10. Five roads lead from N; with the currect time at 8, they would yield these events: "D at 11" (ignored), "Y at 27" (added), "W at 10" (added), "B at 14" (added), and "F at 17" (ignored). Note that although we have "found" B, we have not necessarily found it by the shortest path yet, so must continue.
    1: M at 10
    2: W at 10
    3: Y at 27
    4: X at 22
    5: B at 14
    6:
    7:
    8:      
    9:      
    10:      
    11:      
    12:      
    13:      
    14:      
    15:      
  11. "M at 10" is removed from the heap.
    Time=10, Location=M
    1: W at 10
    2: B at 14
    3: Y at 27
    4: X at 22
    5:
    6:
    7:
    8:      
    9:      
    10:      
    11:      
    12:      
    13:      
    14:      
    15:      
  12. The time is 10, and we are at M. Four roads lead from M, yielding "E at 17" (ignored), "F at 18" (ignored), "B at 17" (ignored), and "Z at 31" (added).
    1: W at 10
    2: B at 14
    3: Y at 27
    4: X at 22
    5: Z at 31
    6:
    7:
    8:      
    9:      
    10:      
    11:      
    12:      
    13:      
    14:      
    15:      
  13. Round the loop again, and "W at 10" is removed.
    Time=10, Location=W
    1: B at 14
    2: X at 22
    3: Y at 27
    4: Z at 31
    5:
    6:
    7:
    8:      
    9:      
    10:      
    11:      
    12:      
    13:      
    14:      
    15:      
  14. The time is still 10, but now we are at W. Two roads lead out of W, yielding "C at 11" (added), and "N at 12" (ignored).
    1: C at 11
    2: B at 14
    3: Y at 27
    4: Z at 31
    5: X at 22
    6:
    7:
    8:      
    9:      
    10:      
    11:      
    12:      
    13:      
    14:      
    15:      
  15. Notice how the new event, "C at 11" jumped straight to the front, pushing past our previously scheduled arrival at B at 14.
  16. Round the loop, and "C at 11" is removed from the heap.
    Time=11, Location=C
    1: B at 14
    2: X at 22
    3: Y at 27
    4: Z at 31
    5:
    6:
    7:
    8:      
    9:      
    10:      
    11:      
    12:      
    13:      
    14:      
    15:      
  17. The time is now 11 and we are at C. Three roads out of C, giving new events "Z at 20" (improvement), "W at 12" (ignored), and "B at 13" (improvement). B was already at the top, so the improvement didn't move it, but Z gets shifted up to a better position.
    1: B at 13
    2: Z at 20
    3: Y at 27
    4: X at 22
    5:
    6:
    7:
    8:      
    9:      
    10:      
    11:      
    12:      
    13:      
    14:      
    15:      
  18. Round the loop again, "B at 13" is removed. We have reached B, and 13 is guaranteed to be the shortest distance from A. We could stop right now. Who cares about all the other distances?
    Time=13, Location=B
    1: Z at 20
    2: X at 22
    3: Y at 27
    4:
    5:
    6:
    7:
    8:      
    9:      
    10:      
    11:      
    12:      
    13:      
    14:      
    15:      
  19. If we do continue, nothing much happens. First "Z at 20" gets removed. It produces two events, "M at 41" and "C at 29", both are ignored.
    Time=20, Location=Z
    1: X at 22
    2: Y at 27
    3:
    4:
    5:
    6:
    7:
    8:      
    9:      
    10:      
    11:      
    12:      
    13:      
    14:      
    15:      
  20. Then "X at 22" is removed, producing "D at 39" and "Y at 27", both ignored.
    Time=22, Location=X
    1: Y at 27
    2:
    3:
    4:
    5:
    6:
    7:
    8:      
    9:      
    10:      
    11:      
    12:      
    13:      
    14:      
    15:      
  21. Then "Y at 27" is removed, ...
    Time=27, Location=Y
    ... and the heap is empty. But we must not stop yet. "Y at 27" must be dealt with, and it could produce new events, resulting in the heap being unemptied again. The events resulting from "Y at 27" are "X at 32" and "N at 46", both of which are ignored. So the heap stays empty.
    1:
    2:
    3:
    4:
    5:
    6:
    7:
    8:      
    9:      
    10:      
    11:      
    12:      
    13:      
    14:      
    15:      
  22. And it's all over.
Just keep the ETAs that each city had when it was removed from the heap. They are: These are the lengths of the shortest paths from A to each of those places. Look at the original map, and you'll see they are right.

The shortest path from A to B is A-D-N-W-C-B. Notice that the greedy algorithm (always follow the shortest road out of the current city) would not have worked, it would have taken us straight from A to F then to M, then to E, and so on and so on.