Понимание функций фильтрации вверх и вниз в кучах (приоритетных очередях)

У меня возникли некоторые проблемы с кодом для перколяции вверх и вниз в минимальной куче (самый маленький ключ сверху). Моя самая большая претензия связана с циклами for этих двух фрагментов кода, из-за которых я не понимаю остальную часть кода...

int hole = ++currentSize;
Comparable copy = x;

array[ 0 ] = std::move( copy ); //in the books implementation the zero 
//index is kept empty, is this to create a temporary place for the added element?
for( ; x < array[ hole / 2 ]; hole /= 2 ) //my biggest problem is understanding this for loop!!!
    array[ hole ] = std::move( array[ hole / 2 ] ); //what does this do?
array[ hole ] = std::move( array[ 0 ] );

Я не понимаю цикл for здесь. Это может быть связано с такими отношениями, как родитель i-го индекса в i/2 и т. д., но я ничего не знаю об этом. Это для вставки элемента в кучу. Приветствуется любая помощь в разъяснении значения кода.

Затем есть просачивание для метода findMin, для которого я снова не понимаю код.

/**
    * Internal method to percolate down in the heap.
    * hole is the index at which the percolate begins.
    */
void percolateDown( int hole )
{
    int child;
    Comparable tmp = std::move( array[ hole ] );

    for( ; hole * 2 <= currentSize; hole = child ) //not clear with this for loop!!!
{
    child = hole * 2;
    if( child != currentSize && array[ child + 1 ] < array[ child ] )
    ++child;
    if( array[ child ] < tmp )
    array[ hole ] = std::move( array[ child ] );
    else
        break;
    }
    array[ hole ] = std::move( tmp );
    } //somewhat understood, except the for loop...

В основном цикл for, но также какая часть кода что делает? Извиняюсь, если в вопросе есть дилетантство.


c++ algorithm data-structures heap
person studious    schedule 18.04.2015    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Как вы говорите: родитель элемента i находится в i/2. Что делает код, так это вставляет «отверстие», в которое будет помещен новый элемент. Строка в цикле for:

array[ hole ] = std::move( array[ hole / 2 ] );

перемещает родителя в местонахождение дочернего элемента (которое было «дырой»). Итак, что мы в основном делаем, это следующее

while (element being moved up < parent)
    move parent to current index
    current index = index of parent
place element at current index

Другая часть кода делает обратное. Это немного сложнее, потому что хотя у каждого элемента есть только один родитель, у него может быть два дочерних элемента. Первый находится по адресу i * 2, второй по адресу i * 2 + 1. Сначала мы проверяем, есть ли у элемента дочерние элементы (child != currentSize). Мы хотим поменять родителя на дочернего только в том случае, если дочерний элемент меньше. Итак, смотрим, какой ребенок самый маленький (array[ child + 1 ] < array[ child ]). Мы сравниваем этот ребенок с его родителем: если он меньше, мы обмениваем их и продолжаем, иначе мы закончили. Наконец, мы помещаем элемент, который мы перемещали, обратно в «отверстие».

person Jordi Vermeulen    schedule 18.04.2015