Процесс продолжается до тех пор, пока узел с новым элементом не окажется больше либо равным значению родительского узла (как на рис. 14.5) либо пока он не поднимется на самую вершину кучи. Если процесс начинается при условии, что истинно высказывание heap(l, п-1), то к его завершению становится истинным высказывание heap(l, п).
Получив представление о работе функции, займемся ее кодированием. Процесс просеивания указывает на необходимость организовать цикл, поэтому мы сформулируем инвариант цикла. Из рис. 14.5 видно, что свойство кучи выполняется везде в дереве, за исключением узла с новым элементом и его родителя. Если i — индекс нового узла, то мы можем использовать следующий инвариант:
1 оор
/* инвариант heap(1. п) за исключением, возможно, узла i и его роди-
теля */
Поскольку изначально истинно утверждение heap(l, п-1), мы можем инициализировать цикл присваиванием i = п.
В цикл нужно вставить проверку необходимости продолжения работы. Работа считается завершенной, если обрабатываемый элемент достиг вершины кучи или если он больше либо равен значению родительского узла. Инвариант утверждает, что свойство кучи сохраняется для всех элементов, за исключением, быть может, данного элемента и его родителя. Если верно условие i == 1, тогда у узла i нет родителя и свойство кучи выполняется везде, поэтому цикл можно завершить. Если у i есть родитель, мы присваиваем переменной р его индекс: р = i/2. Если x[p]<=x[i], тогда свойство кучи выполняется везде и цикл можно завершить.
Если, напротив, элемент i и его родитель находятся в неправильном соотношении, тогда мы меняем их местами (элементы x[i] и х[р]). Этот шаг показан на рис. 14.6.
Рис. 14.6. Перестановка узлов, стоящих в неправильном порядке
После перестановки все пять элементов оказываются в правильном порядке: b < d и b < е, поскольку изначально элемент b был расположен выше . Далее, а < Ь, поскольку условие х[р] <= x[i] не выполнилось, и а < с, поскольку а < b, а b < с. Таким образом, свойство кучи оказывается выполненным везде в массиве, за исключением, быть может, элемента р и его родителя, поэтому мы восстанавливаем инвариант, выполняя присваивание i = р.
Собрав все это вместе, получим функцию, представленную в листинге 14.1, которая выполняется за время, пропорциональное log и, поскольку именно столько уровней имеется в куче.
Листинг 14.1. Функция просеивания нового элемента вверх
void siftup(n)
предусловие: п > 0 && heapCl. п-1) постусловие: heap(l.n)
1 оор
/* инвариант he а р С1. п) за исключением, быть может, элемента i
и его родителя */ if i == 1
break р = 1/2
i f х[р] <= х[1 ] break swap(р. i) i = р
Как и в главе 4, предусловия и постусловия характеризуют функцию. Если предусловие истинно до вызова функции, то постусловие окажется истинным после возврата из нее.
От просеивания вверх перейдем к просеиванию вниз. Если х[1. .п] — куча, а мы присваиваем элементу х[1] новое значение, то в любом случае остается верным утверждение heap(2, п). Функция siftdown предназначена для расширения этого утверждения до heap(l, п). Это осуществляется путем просеивания элемента х[1] вниз по массиву, до тех пор, пока у него не закончатся дочерние элементы или пока элемент не окажется не превышающим значений всех его дочерних элементов. На рис. 14.7 элемент 18 просеивается вниз до тех пор, пока он не станет меньшим его единственного дочернего элемента (19).
Когда элемент просеивается вверх (всплывает), он всегда движется к корню дерева. Когда элемент просеивается вниз (тонет), процесс может быть более сложным: стоящий не на своем месте элемент обменивается с меньшим из своих дочерних элементов. |
Главная
Каталог файлов
