Объяснение строки кода кучи

Question

if (index != indexMaxim)
{
    Rezervare aux = heap.vectorRezervari[index];
    heap.vectorRezervari[index] = heap.vectorRezervari[indexMaxim];
    heap.vectorRezervari[indexMaxim] = aux;

    if (indexMaxim < (heap.nrElements - 1) / 2) // I REALLY DONT GET WHAT THAT MEAN...
        filtrareHeap(heap, indexMaxim);
}

Я работаю над структурой кучи и думаю, что эта строка предназначена для сравнения значения indexMaxim с родительским узлом, поэтому, если значение меньше, чем метод filtrareHeap (), вызывается для обмена индексами.

Можете ли вы дать мне более конкретное объяснение?

Answer 1

В размещенной в нуле куче, размещенной в массиве, размером n, где n > 0 остается верным, если любой индекс родительского узла i такой, что i находится в [0,n-1], где n - эточисло узлов кучи, соответствующие дочерние узлы могут быть найдены в:

2 * i + 1
2 * (i + 1)

в том случае, когда каждый из вышеперечисленных аналогично в [0,n-1]

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

Учитывая кучу размера 7, уравнение дает 3. И это имеет смысл, потому что, учитывая индексы

0 1 2 3 4 5 6

, мы знаем, что

• 0 является родительским1,2
• 1 является родителем 3,4
• 2 является родителем 5,6

Следовательно, первый узел, который будет иметь дочерних элементов в дереве - 3. Условие, которое вы задаете, просто определяет, меньше ли узел этой позиции, и если это так, предпримите дальнейшие действия;в противном случае остановитесь.

Answer 2

Условный флаг, который вы проверяете, проверяет, соответствует ли indexMaxim внутреннему узлу кучи, а не конечному узлу.Если это внутренний узел, то значение может потребоваться отфильтровать дальше, отсюда (рекурсивный?) Вызов filtrareHeap(), но если это листовой узел, то значение не может идти дальше этого узла.