Разбиране на функциите за перколиране нагоре и надолу в Heaps (приоритетни опашки)

Имам някои проблеми с кода за percolate нагоре и надолу в min-heap (най-малкият ключ отгоре). Най-голямото ми недоволство е с 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 и т.н., но не съм наясно с това. Това е за вмъкване на елемент в купчината. Оценява се всяка помощ при излагането на значението на кода.

След това има percolate down за метода 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