Листинг 14.4. Добавление нового элемента в очередь с приоритетом
void 1nsert(t) if n >= maxsize
/ * вывести сообщение об ошибке */
n + +
x[n] = t
/* heap( 1. n-1) */ siftup(n) heap(1. n)
Функция extract mi n находит наименьший элемент набора, удаляет его, а затем производит реструктурирование массива для восстановления свойства кучи. Поскольку массив является кучей, его наименьший элемент — х[1]. Оставшиеся п-1 элементов набора находятся в подмассиве х[2..п], обладающем свойством кучи. Истинность высказывания heap(l, п) восстанавливается в 2 этапа. Сначала х[п] перемещается в х[1] и уменьшается п, после чего элементы набора снова находятся в подмассиве х[1..п], а высказывание heap(2, п) оказывается истинным. На втором этапе мы вызываем функцию siftdown, которая и восстанавливает истинность heap(l, п). Код функции extractmin получился простым. Он приведен в листинге 14.5.
Листинг 14.5. Функция извлечения наименьшего элемента из очереди с приоритетом
1nt extractmiп()
1 f п < 1
/* вывести сообщение об ошибке */
t - х[ ID
Х[1] = х[п--]
/* heap(2, n) */ siftdown(n)
/* heap(1. n) */ return t
Функции insert и extractmin на куме размерностью n выполняются за время О(п). В листинге 14.6 приведен полный код реализации очереден с приоритетом па C++.
Опубликовал vovan666
April 17 2013 00:04:18 ·
0 Комментариев ·
4339 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
