Page 58 - 6110

Розглядають два види бінарних куп: неспадні і незростаючі. В
обох видах значення, що розташовані у вузлах купи, задовільняють
властивості купи (heap property). Властивість незростаючої купи
(max-heap property) полягає в тому, що для кожного вузла крім
кореневого виконується нерівність:

.

Іншими словами, значення вузла не перевищує значення
батьківського вузла. Таким чином найбільший елемент знаходиться
в корені дерева. Принцип побудови неспадної купи (min-heap)
протилежний. Властивість неспадної купи (min-heap property)
полягає в тому, що кожен елемент крім кореневого є неменшим за
свій батьківський елемент:

.

Підтримку властивості купи можна здійснювати за допомогою
процедури Max_Heapify (для незростаючих бінарних куп). На
вхід подається масив A й індекс i цього масиву. При виклику
процедури Max_Heapify припускається, що бінарні дерева,
коренями яких є елементи Left(i) і Right(i) є незростаючими
купами, але сам елемент A[i] може бути меншим за його дочірні
елементи і тим самим порушувати властивість незростаючої купи.
Процедура Max_Heapify спускає значення елемента A[i] вниз
по купі до тих пір, доки дерево в якому цей елемент буде корнем не
стане незростаючою бінарною купою:

Max_Heapify(A,i)

1
2
3 if і A[l] > A[i]
4 then
5 else

6 if і A[r] > A[largest]
7 then

57