¿Error en la PriorityQueue <T> interna de Microsoft?

En .NET Framework en PresentationCore.dll, hay una PriorityQueue<T>clase genérica cuyo código se puede encontrar aquí .

Escribí un programa corto para probar la clasificación y los resultados no fueron excelentes:

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();
        }
    }
}

Resultados:

2789658
3411390
4618917
6996709
found sorting error
6381637
9367782

Hay un error de clasificación y, si se aumenta el tamaño de la muestra, el número de errores de clasificación aumenta de forma algo proporcional.

¿Hice algo malo? Si no es así, ¿dónde se PriorityQueueencuentra exactamente el error en el código de la clase?

El comportamiento se puede reproducir utilizando el vector de inicialización [0, 1, 2, 4, 5, 3]. El resultado es:

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

(podemos ver que 3 está colocado incorrectamente)

El Pushalgoritmo es correcto. Construye un min-heap de una manera sencilla:

• Empiece desde abajo a la derecha
• Si el valor es mayor que el nodo principal, insértelo y regrese
• De lo contrario, coloque el padre en la posición inferior derecha, luego intente insertar el valor en el lugar del padre (y siga intercambiando el árbol hasta que se encuentre el lugar correcto)

El árbol resultante es:

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

El problema está en el Popmétodo. Comienza considerando el nodo superior como un "espacio" para llenar (ya que lo abrimos):

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

Para llenarlo, busca el hijo inmediato más bajo (en este caso: 1). Luego mueve el valor hacia arriba para llenar el espacio (y el niño ahora es el nuevo espacio):

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

Luego hace exactamente lo mismo con el nuevo espacio, por lo que el espacio se mueve hacia abajo nuevamente:

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

Cuando el espacio ha llegado al final, el algoritmo ... toma el valor del extremo inferior derecho del árbol y lo usa para llenar el espacio:

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

Ahora que la brecha está en el nodo de la parte inferior derecha, disminuye _countpara eliminar la brecha del árbol:

                 1
               /   \
              /     \
             4       2
           /  \     
          3    5   

Y terminamos con ... Un montón roto.

Para ser perfectamente honesto, no entiendo qué estaba tratando de hacer el autor, así que no puedo arreglar el código existente. A lo sumo, puedo cambiarlo con una versión funcional (copiado descaradamente de Wikipedia ):

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);
    }
}

El problema principal con ese código es la implementación recursiva, que se romperá si el número de elementos es demasiado grande. En su lugar, recomiendo encarecidamente utilizar una biblioteca de terceros optimizada.

Editar: Creo que descubrí lo que falta. Después de tomar el nodo de la parte inferior derecha, el autor simplemente se olvidó de reequilibrar el montón:

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--;
}

La respuesta de Kevin Gosse identifica el problema. Aunque su reequilibrio del montón funcionará, no es necesario si soluciona el problema fundamental en el ciclo de eliminación original.

Como señaló, la idea es reemplazar el elemento en la parte superior del montón con el elemento más bajo, más a la derecha, y luego tamizarlo hacia la ubicación adecuada. Es una simple modificación del bucle original:

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);
    }
}

Tenga en cuenta también que el código tal como está escrito tiene una pérdida de memoria. Este fragmento de código:

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

No borra el valor de _heap[_count - 1]. Si el montón está almacenando tipos de referencia, las referencias permanecen en el montón y no se pueden recolectar como basura hasta que la memoria del montón sea como basura. No sé dónde se usa este montón, pero si es grande y tiene una vida útil significativa, podría causar un consumo excesivo de memoria. La respuesta es borrar el elemento después de copiarlo:

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

Mi código de reemplazo incorpora esa solución.

No reproducible en .NET Framework 4.8

Intentando reproducir este problema en 2020 con la implementación de .NET Framework 4.8 del PriorityQueue<T>enlace de la pregunta utilizando la siguiente XUnitprueba ...

public class PriorityQueueTests
{
    [Fact]
    public void PriorityQueueTest()
    {
        Random random = new Random();
        // Run 1 million tests:
        for (int i = 0; i < 1000000; i++)
        {
            // Initialize PriorityQueue with default size of 20 using default comparer.
            PriorityQueue<int> priorityQueue = new PriorityQueue<int>(20, Comparer<int>.Default);
            // Using 200 entries per priority queue ensures possible edge cases with duplicate entries...
            for (int j = 0; j < 200; j++)
            {
                // Populate queue with test data
                priorityQueue.Push(random.Next(0, 100));
            }
            int prev = -1;
            while (priorityQueue.Count > 0)
            {
                // Assert that previous element is less than or equal to current element...
                Assert.True(prev <= priorityQueue.Top);
                prev = priorityQueue.Top;
                // remove top element
                priorityQueue.Pop();
            }
        }
    }
}

... tiene éxito en los 1 millón de casos de prueba:

Entonces parece que Microsoft solucionó el error en su implementación:

internal void Pop()
{
    Debug.Assert(_count != 0);
    if (!_isHeap)
    {
        Heapify();
    }

    if (_count > 0)
    {
        --_count;

        // discarding the root creates a gap at position 0.  We fill the
        // gap with the item x from the last position, after first sifting
        // the gap to a position where inserting x will maintain the
        // heap property.  This is done in two phases - SiftDown and SiftUp.
        //
        // The one-phase method found in many textbooks does 2 comparisons
        // per level, while this method does only 1.  The one-phase method
        // examines fewer levels than the two-phase method, but it does
        // more comparisons unless x ends up in the top 2/3 of the tree.
        // That accounts for only n^(2/3) items, and x is even more likely
        // to end up near the bottom since it came from the bottom in the
        // first place.  Overall, the two-phase method is noticeably better.

        T x = _heap[_count];        // lift item x out from the last position
        int index = SiftDown(0);    // sift the gap at the root down to the bottom
        SiftUp(index, ref x, 0);    // sift the gap up, and insert x in its rightful position
        _heap[_count] = default(T); // don't leak x
    }
}

Como el enlace en las preguntas solo apunta a la versión más reciente del código fuente de Microsoft (actualmente .NET Framework 4.8), es difícil decir qué se cambió exactamente en el código, pero lo más notable es que ahora hay un comentario explícito para no perder memoria, por lo que podemos suponga que la pérdida de memoria mencionada en la respuesta de @ JimMischel también se ha abordado, lo que se puede confirmar con las herramientas de diagnóstico de Visual Studio:

Si hubiera una pérdida de memoria, veríamos algunos cambios aquí después de un par de millones de Pop()operaciones ...