Почему эта функция подкачки ведет себя непоследовательно в реализации кучи? - PullRequest
0 голосов
/ 31 марта 2020

Вот куча до уменьшения с 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);
}

Я попытался отладить печатью флагов. Функция вводит своп, и своп, кажется, сделан. Но как-то это не отражается и я понятия не имею, почему.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...