Ok, I see a couple of the things I was doing wrong (outputting the heap map inside a loop where it was changing, and outputting the heap map values after the queue had been emptied (I understand now that they are all set to (size_t)(-1)). Here is a more correct version: http://ideone.com/cZosV Unfortunately, it still doesn't work :( Here is the output: Initial heap map Index: 4294967295 Index: 4294967295 Index: 4294967295 Index: 4294967295 There are 0 items in the queue. Original priority for 0, 0 316 Index added: 0 Original priority for 1, 0 493 Index added: 1 Original priority for 0, 1 488 Index added: 2 Original priority for 1, 1 867 Index added: 3 Heap map after initial pushes: Index: 1 Index: 3 Index: 2 Index: 0 There are 4 items in the queue. New priority for 0, 0 724 New priority for 1, 0 753 New priority for 0, 1 577 New priority for 1, 1 127 Heap map after updates: Index: 1 Index: 3 Index: 2 Index: 0 There are 4 items in the queue. vertex: 1 1 priority: 127 vertex: 1 0 priority: 753 vertex: 0 0 priority: 724 vertex: 0 1 priority: 577 Heap map at end: Index: 4294967295 Index: 4294967295 Index: 4294967295 Index: 4294967295 You can see that these priorities that are output in the last loop are not sorted. They seem to be sorted on most runs, but 1 out of 5 or so seems to produce these unordered priorities. What can we try next :) ? David