за исключением, быть может, интервала между узлом I и его "отцом". Поэтому мы вновь достигнем инварианта, присваивая I := Р.
Из вышеприведенных фрагментов формируется программа SiftUp, время работы которой пропорционально logN, так как пирамида имеет logN уровней.
procedure SiftUp(N)
pre Heap(l,N-l) и N > 0 /* На входе */
post Heapd.N) /* На выходе #/
I := N
loop
Л Инвариант: функция Неар(1,Ю истинна, за исключением,
возмохно, участка от I до его "отца" </
if I = 1 then break
Р :: I div 2
if XCP3 <= ХСП then break
SwaptXCP], ХСП)
I := P
Как и в гл. 4, строки pre (на входе) и post (на выходе) характеризуют эту процедуру: если условие pre имеет место перед вызовом процедуры, то условие post устанавливается после ее завершения.
Присваивание элементу, X [1] нового значения при условии, что массив X [1. . .N] является пирамидой, сохраняет истинность функции Heap (2, N); процедура SiftDown (сдвиг вниз) восстанавливает истинность функции Heap (1, N), сдвигая элемент X [1] вниз в массиве до тех пор, пока у него не окажется "сыновей" или пока он больше своих "сыновей". На следующем рисунке показан узел 02, который сдвигается вниз по пирамиде до тех пор, пока его значение не станет, наконец, меньше значения его единственного "сына" (узла 19):
15 15
