On Wed, Sep 5, 2012 at 11:59 AM, Alex Hagen-Zanker
On 05/09/2012 16:14, David Doria wrote:
but the output is still really wacky
I am not sure, but it appears that when you update the priority of a vertex, it might just as well be an increased or a decreased priority.
The algorithm on the other hand appears to expect that priorities only increase.
update() as well as push_or_update() only call preserve_heap_property_up(index) and not preserve_heap_property_down(index).
Again, I am not sure... do check.
I would like the heap to remain copyable!
Alex
Ah, you got it! This code produces the problem repeatably: http://codepad.org/H2Mnqt8j (no randomness, the values that were producing an incorrect result are hard-coded). The output with the existing algorithm is: The priority queue is: vertex: 1 1 priority: 514 vertex: 0 1 priority: 793 vertex: 0 0 priority: 355 vertex: 1 0 priority: 12 Then I changed the update function from: preserve_heap_property_up(index); to preserve_heap_property_up(index); preserve_heap_property_down(); and ran it again. The output is now correct!: The priority queue is: vertex: 0 1 priority: 793 vertex: 1 1 priority: 514 vertex: 0 0 priority: 355 vertex: 1 0 priority: 12 Can we add a function that does this? In fact, the update() function seems like it could be renamed to increase_priority() or something, while the new function (with update up and down) would be just "update()". Thoughts? David