Вот куча до уменьшения с 15 до 13.
|
99
/ \
10 15
/ \ / \
7 9 11 14
/ \ / \ / \ / \
1 4 3 8 2 6 5 12
Это куча после уменьшения ключа от 15 до 13. Вы видите, что проблема в том, что 13 не выпадает, как ожидалось. (похоже, что swap работает для пузыря)
Decreasing the key 15 to 13
Heap Array:99 10 13 7 9 11 14 1 4 3 8 2 6 12 5
|
99
/ \
10 13
/ \ / \
7 9 11 14
/ \ / \ / \ / \
1 4 3 8 2 6 12 5
Это вспомогательный код для уменьшения ключа в куче.
Идет от кнопки уменьшения -> _lookfor -> _bubbleDown -> _swap.
template <class T>
void Heap<T>::_bubbleDown(int index) {
if (index >= _n) return; // end of array
while (_heap[index] < _heap[(index*2)+1] || _heap[index] < _heap[(index*2)+2]) { // index < child. bubble down the index.
int biggerChild = ((_heap[(index*2)+1] > _heap[(index*2)+2]) ? (index*2)+1 : (index*2)+2);
_swap(_heap[index], _heap[biggerChild]);
index = biggerChild;
if (index >= _n) break;
}
}
template <class T>
void Heap<T>::_swap(int x, int y) {
T temp;
temp = _heap[x];
_heap[x] = _heap[y];
_heap[y] = temp;
}
template <class T>
int Heap<T>::_lookFor(T x){ // not a very good implementation, but just use this for now.
int i;
for(i=0;i<_n;i++)
if (_heap[i] == x)
return i;
return -1;
}
template <class T>
void Heap<T>::decreaseKey(T from, T to)
{
int index = _lookFor(from);
if (index == -1) return;
else {
_heap[index] = to;
}
_bubbleDown(index);
}
Я попытался отладить печатью флагов. Функция вводит своп, и своп, кажется, сделан. Но как-то это не отражается и я понятия не имею, почему.