В этом разделе мы рассмотрим две функции, восстанавливающие массивы, свойство «кучности» которых было нарушено на одном из концов. Обе функции являются эффективными: для реорганизации кучи из п элементов обе они требуют примерно log п шагов. Учитывая построение главы, функции будут определены в этом разделе, а использованы в следующем.
Добавление произвольного элемента в поле х[п] при условии, что х[1..п-1] является кучей, не обязательно даст кучу heap (1, п). Восстановление свойства кучи (то есть распространение его на новый элемент) обеспечивается функцией siftup (просеивание вверх). Имя функции оиисывает стратегию, лежащую в ее основе: новый элемент просеивается и всплывает вверх до полагающегося ему места, обмениваясь позициями с вышестоящими элементами. В этом разделе используется типичное определение кучи, в котором новый элемент движется вверх: х[1] находится наверху кучи, поэтому х[п] находится внизу. Процесс иллюстрируется рис. 14.5, на котором (слева направо) показан процесс подъема нового элемента 13 вверх но дереву, пока ои не оказывается на подобающем ему месте в качестве узла первого уровня.
Опубликовал vovan666
April 17 2013 00:04:07 ·
0 Комментариев ·
2624 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
