Le problème peut être reproduit en utilisant le vecteur d'initialisation [0, 1, 2, 4, 5, 3]. Le résultat est:
[0, 1, 2, 4, 3, 5]
(nous pouvons voir que 3 est mal placé)
L' Push algorithme est correct. Il construit un min-segment d'une façon simple:
- Commencer en bas à droite
- Si la valeur est plus grande que le nœud parent puis de l'insérer et de retour
- Sinon, mis à la place du parent dans le bas à droite de position, puis essayez d'insérer la valeur à la place des parents (et de garder la permutation de l'arbre jusqu'à ce que la place a été trouvé)
L'arbre résultant est:
0
/ \
/ \
1 2
/ \ /
4 5 3
Le problème avec l' Pop méthode. Il commence par examiner le nœud supérieur comme un "écart" à remplir (depuis que nous avons sauté):
*
/ \
/ \
1 2
/ \ /
4 5 3
Pour le remplir, il recherche pour le plus immédiat de l'enfant (dans ce cas: 1). Il se déplace ensuite la valeur de combler l'écart (et l'enfant est désormais le nouveau gap):
1
/ \
/ \
* 2
/ \ /
4 5 3
Il fait ensuite la même chose avec la nouvelle écart, de sorte que l'écart se déplace vers le bas à nouveau:
1
/ \
/ \
4 2
/ \ /
* 5 3
Lorsque l'écart a atteint le fond, l'algorithme... prend les bas-droite de la valeur de l'arbre et l'utilise pour combler l'écart:
1
/ \
/ \
4 2
/ \ /
3 5 *
Maintenant que l'écart est en bas à droite du nœud, il décrémente _count pour supprimer l'écart de l'arbre:
1
/ \
/ \
4 2
/ \
3 5
Et nous nous retrouvons avec... Une fracture de la tas.
Pour être parfaitement honnête, je ne comprends pas ce que l'auteur a essayé de le faire, donc je ne peux pas corriger le code existant. Tout au plus, je peux l'échanger avec une version de travail (copié sans vergogne de Wikipédia):
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);
}
}
Problème principal de ce code est récursive de la mise en œuvre, ce qui va casser si le nombre d'éléments est trop importante. Je recommande fortement d'utiliser une optimisation du tiers de la bibliothèque de la place.
Edit: je crois que j'ai trouvé ce qui fait défaut. Après la prise de la bas-nœud le plus à droite, l'auteur a juste oublié de rééquilibrer le tas:
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--;
}
