Priority queues return out-of-order values after removing an internal item

Release Type: GitHub source

Version: 3d034317171905c1889fd6b3820d648b2af73312

Platform(s): Reproduced on Linux using .NET SDK 10.0.100. This is managed collection code; no graphics or editor execution is required for the reproduction.

Describe the bug

PriorityQueue<T>.Remove and PriorityNodeQueue<T>.Remove can break priority order when removing an internal item. They replace the removed slot with the last element and only repair downward. When that replacement is smaller than its new parent, it must move upward instead.

To Reproduce

Run this against the Stride.Core queue implementation at the commit above:

var queue = new Stride.Core.Collections.PriorityQueue<int>();
foreach (var value in new[] { 0, 1, 4, 2, 5, 6, 7, 3 })
    queue.Enqueue(value);

queue.Remove(5);

while (!queue.Empty)
    Console.WriteLine(queue.Dequeue());

Actual output: 0, 1, 2, 4, 3, 6, 7.

Expected behavior

Output remains in priority order: 0, 1, 2, 3, 4, 6, 7.

The same input reproduces with PriorityNodeQueue<int> when removing the node returned by Enqueue(5). Both variants also fail under a descending custom comparer.

var queue = new Stride.Core.Collections.PriorityNodeQueue<int>();
Stride.Core.Collections.PriorityQueueNode<int>? nodeToRemove = null;
foreach (var value in new[] { 0, 1, 4, 2, 5, 6, 7, 3 })
{
    var node = queue.Enqueue(value);
    if (value == 5)
        nodeToRemove = node;
}

queue.Remove(nodeToRemove!);

while (!queue.Empty)
    Console.WriteLine(queue.Dequeue());

Screenshots

Not applicable; the reproduction is a console collection test.

Log and callstacks

The regression assertion fails at the fourth dequeued value:

Assert.Equal() Failure: Values differ
Expected: 3
Actual:   4

Original production sources: Total tests: 14; Passed: 8; Failed: 6
Patched production sources:  Total tests: 14; Passed: 14; Failed: 0

Additional context

These are active engine paths: Scheduler.Unschedule removes empty priority buckets, AnimationChannel.Fitting removes queued error nodes, and AssetBuilderService.RemoveBuildUnit removes queue nodes. The collection-level ordering failure is verified; I have not run the editor or claimed a particular visible scene failure.

A prepared patch with regression tests repairs upward when needed while preserving the existing heap representation and maintaining both node indices on swaps. It includes six new regression cases: the eight-item example under both comparer directions, plus deterministic shuffled insertion/removal coverage for both queue variants. Compiling the three real production files and the two existing test files in an isolated xUnit project produced 8 passed / 6 failed before, then 14 passed / 0 failed after. No collection implementation was mocked or rewritten in the harness. The ordinary repository test invocation did not produce a final result in the captured log, so I am not claiming a passing engine build or full repository suite.

AI disclosure: OpenAI Codex prepared this investigation, patch, and executable regression tests for falseee1.

Start at the Stride.Core.Collections PriorityQueue and PriorityNodeQueue Remove entry points, then run the supplied reproduction and existing collection tests. Verify removal preserves priority order for internal items, both queue variants, ascending and descending comparers, and node-index updates; add or run regression coverage for the listed cases.