I think there is something going wrong with the index_in_heap map. I added: std::cout << "Index added: " << get(index_in_heap, v) << std::endl; after this line: put(index_in_heap, v, index); in d_ary_heap_indirect::push(Value). I also added std::cout << "Index added caller: " << get(index_in_heap, v) << std::endl; after the first round of adding values to the queue (after this line: mutableQueue.push(*vertexIterator); The output is: Original priority for 0, 0 641 Index added: 0 Index added caller: 0 Original priority for 1, 0 40 Index added: 1 Index added caller: 1 Original priority for 0, 1 400 Index added: 2 Index added caller: 2 Original priority for 1, 1 664 Index added: 3 Index added caller: 0 I don't understand why this last index is 3 inside the push() function, but 0 when I query it from the caller? When I look at the same things inside the update() function, the index_in_heap just seems to return garbage. That is, I look at the value of size_type index = get(index_in_heap, v); in update(), and when it is called with vertex (0,0), the value of 'index' is 4294967295 (when I would expect it to be in the range [0,3]). Can you explain this? Perhaps I am setting up the index_in_heap map incorrectly? David