Fehler in der internen PriorityQueue <T> von Microsoft?

In .NET Framework in PresentationCore.dll gibt es eine generische PriorityQueue<T>Klasse, deren Code hier zu finden ist .

Ich habe ein kurzes Programm geschrieben, um die Sortierung zu testen, und die Ergebnisse waren nicht großartig:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using MS.Internal;

namespace ConsoleTest {
    public static class ConsoleTest {
        public static void Main() {
            PriorityQueue<int> values = new PriorityQueue<int>(6, Comparer<int>.Default);
            Random random = new Random(88);
            for (int i = 0; i < 6; i++)
                values.Push(random.Next(0, 10000000));
            int lastValue = int.MinValue;
            int temp;
            while (values.Count != 0) {
                temp = values.Top;
                values.Pop();
                if (temp >= lastValue)
                    lastValue = temp;
                else
                    Console.WriteLine("found sorting error");
                Console.WriteLine(temp);
            }
            Console.ReadLine();
        }
    }
}

Ergebnisse:

2789658
3411390
4618917
6996709
found sorting error
6381637
9367782

Es liegt ein Sortierfehler vor, und wenn die Stichprobengröße erhöht wird, nimmt die Anzahl der Sortierfehler etwas proportional zu.

Habe ich etwas falsch gemacht? Wenn nicht, wo befindet sich der Fehler im Code der PriorityQueueKlasse genau?

Das Verhalten kann unter Verwendung des Initialisierungsvektors reproduziert werden [0, 1, 2, 4, 5, 3]. Das Ergebnis ist:

[0, 1, 2, 4, 3, 5]

(Wir können sehen, dass 3 falsch platziert ist)

Der PushAlgorithmus ist korrekt. Es baut auf einfache Weise einen Min-Haufen auf:

• Beginnen Sie unten rechts
• Wenn der Wert größer als der übergeordnete Knoten ist, fügen Sie ihn ein und geben Sie ihn zurück
• Andernfalls setzen Sie stattdessen das übergeordnete Element an die untere rechte Position und versuchen Sie dann, den Wert an der übergeordneten Stelle einzufügen (und tauschen Sie den Baum weiter aus, bis die richtige Stelle gefunden wurde).

Der resultierende Baum ist:

                 0
               /   \
              /     \
             1       2
           /  \     /
          4    5   3

Das Problem ist mit der PopMethode. Es beginnt damit, dass der oberste Knoten als eine "Lücke" betrachtet wird, die gefüllt werden muss (da wir ihn geöffnet haben):

                 *
               /   \
              /     \
             1       2
           /  \     /
          4    5   3

Um es zu füllen, sucht es nach dem niedrigsten unmittelbaren Kind (in diesem Fall: 1). Anschließend wird der Wert nach oben verschoben, um die Lücke zu füllen (und das Kind ist jetzt die neue Lücke):

                 1
               /   \
              /     \
             *       2
           /  \     /
          4    5   3

Es macht dann genau das Gleiche mit der neuen Lücke, sodass sich die Lücke wieder nach unten bewegt:

                 1
               /   \
              /     \
             4       2
           /  \     /
          *    5   3

Wenn die Lücke den Boden erreicht hat, nimmt der Algorithmus ... den Wert ganz rechts unten des Baums und füllt damit die Lücke:

                 1
               /   \
              /     \
             4       2
           /  \     /
          3    5   *

Nachdem sich die Lücke am Knoten ganz rechts unten befindet, wird sie dekrementiert _count, um die Lücke aus dem Baum zu entfernen:

                 1
               /   \
              /     \
             4       2
           /  \     
          3    5   

Und am Ende haben wir ... einen kaputten Haufen.

Um ganz ehrlich zu sein, verstehe ich nicht, was der Autor versucht hat, daher kann ich den vorhandenen Code nicht reparieren. Ich kann es höchstens gegen eine Arbeitsversion austauschen (schamlos aus Wikipedia kopiert ):

internal void Pop2()
{
    if (_count > 0)
    {
        _count--;
        _heap[0] = _heap[_count];

        Heapify(0);
    }
}

internal void Heapify(int i)
{
    int left = (2 * i) + 1;
    int right = left + 1;
    int smallest = i;

    if (left <= _count && _comparer.Compare(_heap[left], _heap[smallest]) < 0)
    {
        smallest = left;
    }

    if (right <= _count && _comparer.Compare(_heap[right], _heap[smallest]) < 0)
    {
        smallest = right;
    }

    if (smallest != i)
    {
        var pivot = _heap[i];
        _heap[i] = _heap[smallest];
        _heap[smallest] = pivot;

        Heapify(smallest);
    }
}

Das Hauptproblem bei diesem Code ist die rekursive Implementierung, die unterbrochen wird, wenn die Anzahl der Elemente zu groß ist. Ich empfehle dringend, stattdessen eine optimierte Drittanbieter-Bibliothek zu verwenden.

Edit: Ich glaube ich habe herausgefunden was fehlt. Nachdem der Autor den Knoten ganz rechts unten genommen hatte, vergaß er nur, den Heap neu auszugleichen:

internal void Pop()
{
    Debug.Assert(_count != 0);

    if (_count > 1)
    {
        // Loop invariants:
        //
        //  1.  parent is the index of a gap in the logical tree
        //  2.  leftChild is
        //      (a) the index of parent's left child if it has one, or
        //      (b) a value >= _count if parent is a leaf node
        //
        int parent = 0;
        int leftChild = HeapLeftChild(parent);

        while (leftChild < _count)
        {
            int rightChild = HeapRightFromLeft(leftChild);
            int bestChild =
                (rightChild < _count && _comparer.Compare(_heap[rightChild], _heap[leftChild]) < 0) ?
                    rightChild : leftChild;

            // Promote bestChild to fill the gap left by parent.
            _heap[parent] = _heap[bestChild];

            // Restore invariants, i.e., let parent point to the gap.
            parent = bestChild;
            leftChild = HeapLeftChild(parent);
        }

        // Fill the last gap by moving the last (i.e., bottom-rightmost) node.
        _heap[parent] = _heap[_count - 1];

        // FIX: Rebalance the heap
        int index = parent;
        var value = _heap[parent];

        while (index > 0)
        {
            int parentIndex = HeapParent(index);
            if (_comparer.Compare(value, _heap[parentIndex]) < 0)
            {
                // value is a better match than the parent node so exchange
                // places to preserve the "heap" property.
                var pivot = _heap[index];
                _heap[index] = _heap[parentIndex];
                _heap[parentIndex] = pivot;
                index = parentIndex;
            }
            else
            {
                // Heap is balanced
                break;
            }
        }
    }

    _count--;
}

Die Antwort von Kevin Gosse identifiziert das Problem. Obwohl sein erneutes Ausbalancieren des Heaps funktioniert, ist es nicht erforderlich, wenn Sie das grundlegende Problem in der ursprünglichen Entfernungsschleife beheben.

Wie er betonte, besteht die Idee darin, den Gegenstand oben auf dem Haufen durch den niedrigsten Gegenstand ganz rechts zu ersetzen und ihn dann an die richtige Stelle zu sieben. Es ist eine einfache Modifikation der ursprünglichen Schleife:

internal void Pop()
{
    Debug.Assert(_count != 0);

    if (_count > 0)
    {
        --_count;
        // Logically, we're moving the last item (lowest, right-most)
        // to the root and then sifting it down.
        int ix = 0;
        while (ix < _count/2)
        {
            // find the smallest child
            int smallestChild = HeapLeftChild(ix);
            int rightChild = HeapRightFromLeft(smallestChild);
            if (rightChild < _count-1 && _comparer.Compare(_heap[rightChild], _heap[smallestChild]) < 0)
            {
                smallestChild = rightChild;
            }

            // If the item is less than or equal to the smallest child item,
            // then we're done.
            if (_comparer.Compare(_heap[_count], _heap[smallestChild]) <= 0)
            {
                break;
            }

            // Otherwise, move the child up
            _heap[ix] = _heap[smallestChild];

            // and adjust the index
            ix = smallestChild;
        }
        // Place the item where it belongs
        _heap[ix] = _heap[_count];
        // and clear the position it used to occupy
        _heap[_count] = default(T);
    }
}

Beachten Sie auch, dass der geschriebene Code einen Speicherverlust aufweist. Dieses Stück Code:

        // Fill the last gap by moving the last (i.e., bottom-rightmost) node.
        _heap[parent] = _heap[_count - 1];

Löscht den Wert nicht aus _heap[_count - 1]. Wenn der Heap Referenztypen speichert, verbleiben die Referenzen im Heap und können erst dann mit Müll gesammelt werden, wenn der Speicher für den Heap mit Müll gesammelt wurde. Ich weiß nicht, wo dieser Heap verwendet wird, aber wenn er groß ist und längere Zeit lebt, kann dies zu einem übermäßigen Speicherverbrauch führen. Die Antwort besteht darin, das Element nach dem Kopieren zu löschen:

_heap[_count - 1] = default(T);

Mein Ersatzcode enthält diesen Fix.