c# - ¿Error en el PriorityQueue<T> interno de Microsoft?

.net priority-queue

Question

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

Escribí un breve programa 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 manera proporcional.

¿Hice algo malo? Si no, ¿dónde se encuentra exactamente el error en el código de la clase PriorityQueue ?

Answer 1

El comportamiento puede reproducirse 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 algoritmo Push es correcto. Construye un montón mínimo de una manera directa:

• Comience desde abajo a la derecha
• Si el valor es mayor que el nodo principal, insértelo y devuelva
• De lo contrario, coloque el padre en la posición inferior derecha, luego intente insertar el valor en el lugar 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 es con el método Pop . Comienza considerando el nodo superior como un "espacio" para llenar (desde 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 vacío (y el niño ahora es el nuevo vacío):

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

Luego hace exactamente lo mismo con la nueva brecha, por lo que la brecha se mueve hacia abajo nuevamente:

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

Cuando la brecha ha llegado al fondo, el algoritmo ... toma el valor inferior derecho del árbol y lo usa para llenar la brecha:

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

Ahora que la brecha está en el nodo inferior _count , disminuye _count para eliminar la brecha del árbol:

                 1
               /   /
              /     /
             4       2
           /  /     
          3    5   

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

Para ser sincero, no entiendo lo que el autor estaba tratando de hacer, así que no puedo arreglar el código existente. A lo sumo, puedo cambiarlo por una versión funcional (copiada 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 utilizar una biblioteca de terceros optimizada.

Editar: creo que descubrí lo que falta. Después de tomar el nodo inferior derecho, el autor simplemente olvidó 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--;
}

Answer 2

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 y más a la derecha, y luego tamizarlo hasta la ubicación adecuada. Es una modificación simple 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 bit 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, entonces las referencias permanecen en el montón y no se pueden recolectar basura hasta que la memoria para el montón sea basura recolectada. No sé dónde se usa este montón, pero si es grande y dura mucho tiempo, 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.