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 el 3 está mal colocado)

El algoritmo Push es correcto. Construye un montón mínimo de una manera sencilla:

• Empezar 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 del padre (y siga cambiando 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 "vacío" para llenar (ya que lo reventamos):

 * / \ / \ 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 la nueva brecha, por lo que la brecha vuelve a bajar:

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

Cuando la brecha ha llegado al fondo, el algoritmo... toma el valor más abajo a la derecha del árbol y lo usa para llenar la brecha:

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

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

 1 / \ / \ 4 2 / \ 3 5

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

Para ser completamente honesto, no entiendo qué estaba tratando de hacer el autor, así que no puedo arreglar el código existente. A lo sumo, puedo cambiarlo por una versión que funcione (descaradamente copiada 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 la cantidad de elementos es demasiado grande. Recomiendo encarecidamente usar una biblioteca de terceros optimizada en su lugar.

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, ie, let parent point to the gap. parent = bestChild; leftChild = HeapLeftChild(parent); } // Fill the last gap by moving the last (ie, 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 y más a la derecha, y luego tamizarlo hasta 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 bit de código:

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

No borra el valor de _heap[_count - 1] . Si el almacenamiento dinámico almacena tipos de referencia, las referencias permanecen en el almacenamiento dinámico y no se pueden recolectar elementos no utilizados hasta que la memoria del almacenamiento dinámico se recolecte como elemento no utilizado. No sé dónde se usa este montón, pero si es grande y vive durante un período de tiempo significativo, podría provocar 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 corrección.

No reproducible en .NET Framework 4.8

Intentando reproducir este problema en 2020 con la implementación de .NET Framework 4.8 de PriorityQueue<T> como se vincula en la pregunta usando la siguiente prueba XUnit ...

 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 solucionado, lo que se puede confirmar con las herramientas de diagnóstico de Visual Studio:

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