Zachowanie można odtworzyć za pomocą wektora inicjalizacyjnego [0, 1, 2, 4, 5, 3]
. Wynik to:
[0, 1, 2, 4, 3, 5]
(widzimy, że 3 jest nieprawidłowo umieszczone)
Push
Algorytm jest poprawny. Buduje min-stertę w prosty sposób:
- Zacznij od prawego dolnego rogu
- Jeśli wartość jest większa niż węzeł macierzysty, wstaw ją i zwróć
- W przeciwnym razie umieść rodzica w prawym dolnym rogu, a następnie spróbuj wstawić wartość w miejscu nadrzędnym (i kontynuuj zamianę drzewa, aż zostanie znalezione właściwe miejsce)
Powstałe drzewo to:
0
/ \
/ \
1 2
/ \ /
4 5 3
Problem dotyczy Pop
metody. Zaczyna się od potraktowania górnego węzła jako „luki” do wypełnienia (odkąd go usunęliśmy):
*
/ \
/ \
1 2
/ \ /
4 5 3
Aby go wypełnić, wyszukuje najniższe bezpośrednie dziecko (w tym przypadku: 1). Następnie przesuwa wartość w górę, aby wypełnić lukę (a dziecko jest teraz nową luką):
1
/ \
/ \
* 2
/ \ /
4 5 3
Następnie robi dokładnie to samo z nową luką, więc luka ponownie się obniża:
1
/ \
/ \
4 2
/ \ /
* 5 3
Kiedy luka osiągnęła najniższy poziom, algorytm ... pobiera skrajną prawą dolną wartość drzewa i wykorzystuje ją do wypełnienia luki:
1
/ \
/ \
4 2
/ \ /
3 5 *
Teraz, gdy przerwa znajduje się w prawym dolnym węźle, zmniejsza się, _count
aby usunąć lukę z drzewa:
1
/ \
/ \
4 2
/ \
3 5
I kończymy z ... Zepsuty stos.
Szczerze mówiąc, nie rozumiem, co autor próbował zrobić, więc nie mogę naprawić istniejącego kodu. Co najwyżej mogę zamienić go na działającą wersję (bezwstydnie skopiowaną z Wikipedii ):
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);
}
}
Głównym problemem z tym kodem jest rekurencyjna implementacja, która zepsuje się, jeśli liczba elementów będzie zbyt duża. W zamian zdecydowanie zalecam używanie zoptymalizowanej biblioteki innej firmy.
Edycja: Myślę, że odkryłem, czego brakuje. Po wybraniu węzła znajdującego się najbardziej na dole po prawej stronie, autor po prostu zapomniał o ponownym zbilansowaniu sterty:
internal void Pop()
{
Debug.Assert(_count != 0);
if (_count > 1)
{
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;
_heap[parent] = _heap[bestChild];
parent = bestChild;
leftChild = HeapLeftChild(parent);
}
_heap[parent] = _heap[_count - 1];
int index = parent;
var value = _heap[parent];
while (index > 0)
{
int parentIndex = HeapParent(index);
if (_comparer.Compare(value, _heap[parentIndex]) < 0)
{
var pivot = _heap[index];
_heap[index] = _heap[parentIndex];
_heap[parentIndex] = pivot;
index = parentIndex;
}
else
{
break;
}
}
}
_count--;
}