Closed adetunji-david closed 5 days ago
Tagging subscribers to this area: @dotnet/area-system-collections See info in area-owners.md if you want to be subscribed.
@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!
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);
}
Description
The newly added
Remove
method inPriorityQueue<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
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