Рисунок 14.7 иллюстрирует также инвариант цикла функции siftdown: свойство кучи остается верным везде, за исключением, быть может, обрабатываемого узла и его дочерних узлов.
1 оор
/* инвариант: heap(1. п) истинно, за исключением, быть может, i и его
дочерних элементов (0. 1 или 2) */
Построение цикла аналогично функции siftup. Сначала нужно проверить, есть ли у i дочерние элементы. Если их нет, цикл завершается. Затем начинаются тонкости: если у i есть дочерние элементы, переменной с присваивается индекс наименьшего из них:. Наконец, мы либо завершаем цикл, если x[i] <« х[с], либо движемся даль- ше к основанию кучи, обменивая местами x[i] и х[с] и выполняя присваивание i = с.
Листинг 14.2. Функция просеивания вниз (siftdown)
void siftdown(n)
предусловие: he а р С 2. п) && п >= 0 #
постусловие: heapC1, п)
i = 1
1 оор
/* инвариант- heapd, п) верно, за исключением, быть может, т и
его дочерних элементов (0. 1 или 2) */ с = 2*1 1 f с > п
break
/* с - левый дочерний элемент i */ if с+1 <= п
/* с+1 - правый дочерний элемент i */
1f х[с+1] < х[с]
C + +
/* с - наименьший из дочерних элементов */ if х[1] <= х[с] break swap(с. i) i = с
Анализ возможных случаев, аналогичный проведенному для функции siftup, показывает, что операция обмена оставляет свойство кучи верным для всех эле* ментов, кроме, быть может, с и его дочерних элементов. Как и siftup, эта функция работает за время, пропорциональное log и, поскольку на каждом из уровней кучи выполняется постоянное количество операций.
Опубликовал vovan666
April 17 2013 00:04:12 ·
0 Комментариев ·
5479 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
