#2 PriorityQueue bug: elements not moved down correctly

[Sabri Al-Safi]

There's a subtle bug regarding how items are moved down the binary heap. When an item is moved down, one of its child items is moved up, however the priority array is not actually updated straight away. This can lead to issues in the next iteration: in line 235 it is possible for the right-hand child to be compared with its former parent (that has been moved up) rather than its new parent (which should have been moved down but hasn't properly done so).

To replicate:

var Q = new PriorityQueue<string, int="">();
Q["one"] = 1;
Q["two"] = 2;
Q["five"] = 5;
Q["three"] = 3;
Q["six"] = 6;
Q["seven"] = 7;
Q["four"] = 4;
var first = Q.Pop(); // Items are in the wrong order after this command.
var second = Q.Peek();
Console.WriteLine(second)</string,>

I suggest writing a Swap(int i, int j) method and performing the full swap for each iteration.

[Sabri Al-Safi]

Apologies, I wrote that code without checking properly, the replication should be:

        PriorityQueue<string, int> Q = new PriorityQueue<string, int>();
        Q["one"] = 1;
        Q["two"] = 2;
        Q["five"] = 5;
        Q["three"] = 3;
        Q["six"] = 6;
        Q["seven"] = 7;
        Q["four"] = 4;
        Q.Pop();
        Q.Pop();
        System.Console.WriteLine(Q.Peek());
        System.Console.Read();

[Balázs Szalkai]

Thanks very much for reporting. I have fixed the issue on the master branch, please pull.