Эффективность
Свойство формы гарантирует, что все узлы кучи находятся не глубже уровня log2 п. Функции siftup и siftdown оказываются эффективными потому, что дерево хорошо сбалансировано. Сортировка с помощью кучи исключает необходимость введения добавочного массива, совмещая две абстрактные структуры (кучу и последовательность) в одном массиве.
Правильность
Чтобы правильно написать цикл, мы начинаем сточной формулировки его инварианта. При выполнении операторов в теле цикла инвариант сохраняется. Свойства формы и порядка представляют собой новую форму инварианта — они являются инвариантными свойствами структуры кучи. При написании функции, работающей с кучей, можно предполагать наличие этих свойств в начале ее работы, причем нужно следить за тем, чтобы свойства эти сохранились к моменту завершения функции.
Абстракция
Хорошие системные инженеры всегда разделяют внешний вид компоненты (абстракцию, видную пользователю) и ее внутреннее устройство (содержимое черного ящика). В этой главе черные ящики заполняются двумя способами: с помощью абстрагирования процедур и типов данных.
Абстрагирование процедур
Функция сортировки может быть использована для сортировки массива без знания ее внутреннего устройства. При этом сортировка рассматривается как одна операция. Функции siftup и siftdown обеспечивают аналогичный уровень абстракции: при построении очередей с приоритетом и программы heapsort мы не заботились о внутреннем устройстве этих функций; нам достаточно было знать, что они делают (реорганизуют массив с нарушенным на одном из концов свойством кучи). Правильный подход к разработке дал нам возможность определить внутренне содержимое черных ящиков однажды, а затем собрать из них две разные программы.
Абстрактные типы данных
Назначение типа данных определяется его методами и описанием этих методов, а соответствие типа данных своему назначению определяется реализацией компонентов. Мы можем воспользоваться классом pnqueue из этой главы или классом IntSet из предыдущей главы, используя только их описание (спецификацию). Конечно, их внутренняя реализация может сказаться на производительности программы.
Опубликовал vovan666
April 17 2013 00:04:28 ·
0 Комментариев ·
2527 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
