PriorityQueue<TElement, TPriority>.Remove method violates min-heap invariant

[adetunji-david]

Description

The newly added Remove method in PriorityQueue<TElement, TPriority> violates the invariant of the internal min-heap structure. The current implementation pops the last element and performs a sift-down operation from the index of the removed element. However, it fails to handle scenarios where the last element should be sifted upwards, resulting in incorrect ordering in the priority queue.

Reproduction Steps

var q = new PriorityQueue<int, int>();
for (var i = 19; i >= 0; i--)
{
    q.Enqueue(i, i);
}

q.Remove(10, out var _, out var _);

while (q.Count > 0)
{
    Console.WriteLine(q.Dequeue());
}

Expected behavior

The code should print numbers from 0 to 19 in ascending order, except for 10.

Actual behavior

It prints 2 between 8 and 9
0
1
3
4
5
6
7
8
2
9
11
12
13
14
15
16
17
18
19

Regression?

No response

Known Workarounds

No response

Configuration

.NET version: 9.0 preview

Other information

No response

[dotnet-policy-service]

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

[jeffhandley]

@krwq can you investigate this issue this week? We should target RC2 snap for this.

Thank you for finding and reporting this with a minimal repro, @adetunji-david!

[ocoanet]

It seems that Remove assumes that the priority of lastNode is always greater than the priority of the removed node, which is not the case. If the priority of lastNode is lower than the priority of the removed node, it should probably be moved up:

if (_comparer == null)
{
    if (Comparer<TPriority>.Default.Compare(priority, lastNode.Priority) < 0)
        MoveDownDefaultComparer(lastNode, index);
    else
        MoveUpDefaultComparer(lastNode, index);
}
else
{
    if (_comparer.Compare(priority, lastNode.Priority) < 0)
        MoveDownCustomComparer(lastNode, index);
    else
        MoveUpCustomComparer(lastNode, index);
}