Q Быстрая сортировка, стандартная реализация (программа 7 1)

М Сортировка слиянием, стандартная реализация (программа 8 1)

PQ Очередь по приоритетам на базе пирамидальной сортировки (программа 9.5)

Н Пирамидальная сортировка, стандартная реализация (программа 9.6)

F Пирамидальная сортировка с усовершенствованием Флойда

Упражнения

9.28. Показать, что пирамидальная сортировка не является устойчивой.

9.29. Определить эмпирическим путем процентное отношение времени, затрачиваемого на фазу построения для N = 10, 10, 10 и 10.

9.30. Реализовать версию пирамидальной сортировки, основанную на полных пирамидально упорядоченных сортирующих деревьях, соответствующих описанным в тексте. Сравнить количество использованных созданной программой операций сравнения, полученное эмпирическим путем, с аналогичным показателем стандартной реализации для N= 10 10 и 10

9.31. Продолжая упражнение 9.30, определить эмпирическим путем, будет ли метод Флойда эффективным применительно к троичным деревьям.

о 9.32. Имея в виду только стоимость операций сравнения и предполагая, что для нахождения наибольшего из / элементов требуется / операций сравнения, найти значение t, которое сводит к минимуму коэффициент N\ogN, присутствующий при подсчете операций сравнения, в том случае, когда в пирамидальной сортировке используется /-арное сортирующее дерево. Сначала воспользуемся прямым обобщением программы 9.7, затем предположим, что метод Флойда позволяет сэкономить одно сравнение во внутреннем цикле.

Таблица 9.2. Эмпирические исследования алгоритмов пирамидальной сортировки

Значения относительного времени выполнения различных видов сортировки на файлах случайных целых чисел подтверждают наши предположения, основанные на оценке длины внутренних циклов, что пирамидальная сортировка обладает меньшим быстродействием, чем быстрая сортировка, но сопоставима по этому параметру с сортировкой слиянием. Временные показатели для первых N страниц книги Moby Dick ( Моби Дик ) в правой части таблицы показывают, что метод Флойда является эффективным усовершенствованием пирамидальной сортировки в тех случаях, когда стоимость операций сравнения достаточно высока.

32-битовые целые ключи строковые ключи

О 9.33. Для N = 32 найти такое расположение ключей, которое требует выполнения максимального числа операций сравнения в рамках пирамидальной сортировки.

9.34. Для N = 32 найти такое расположение ключей, которое требует выполнения минимального числа операций сравнения в рамках пирамидальной сортировки.

9.35. Показать, что построение очереди по приоритетам размером к с последующим выполнением N - к операций заменить наименьший (replace the minimum) (операция вставить плюс операция удалить наименьший), оставляет в сортирующем дереве к наибольших элементов из числа Л элементов.

9.36. Реализовать обе версии выборки на базе пирамидальной сортировки, о которых шла речь при обсуждении леммы 9.6, воспользовавшись методами, описанными в упражнении 9.25. Сравните определяемое эмпирическим путем количество операций сравнения, которые они используют, с аналогичным показателем метода, задействующего быструю сортировку, описанного в разделе главы 7, для Л= 10 и при = 10, 100, 1000, 10\ 10 и 10

9.37. Реализовать версию пирамидальной сортировки, в основу которой положена идея представления пирамидально упорядоченного дерева в прямом порядке (preorder), а не по уровням. Проведите эмпирическое сравнение количества операций сравнения, используемых этой версией, с количеством сравнений в стандартной реализации для ключей с произвольной организацией, причем N = 10, 10 , 10 и 10

9.5. Абарактный тип данных очереди по приоритетам

в большинстве случаев требуется написать приложение так, чтобы оно содержало процедуру реализации очереди по приоритетам вместо того, чтобы возвращать значения из операции удалить наибольший (remove the maximum), уведомлять, тшая из записей обладает наибольшим приоритетом, и подобным же образом поступать по отношению к другим операциям. Другими словами, устанавливаются приоритеты, а очереди по приоритетам применяются только с целью доступа к другой информации в соответствующем порядке. Подобного рода организация аналогична использованию понятий непрямой сортировки (indirect-sort) и сортировки по указателю (pointer-sort), описанных в главе 6. В частности, такой подход нужен для придания смысла таким операциям, как изменить приоритет (change priority) или удалить (remove). Здесь мы подробно исследуем реализацию упомянутой идеи не только в силу того, что в дальнейшем будем использовать Очередь по приоритетам, но еще и потому, что такая ситуация характерна для проблем, с которыми приходится сталкиваться при разработке интерфейсов и реализаций для абстрактных типов данных (АТД).

Когда мы хотим удалить элемент из очереди по приоритетам, как правильно указать, какой конкретно элемент надо удалить? Когда мы хотим поддерживать сразу несколько очередей по приоритетам, как следует организовать реализации, чтобы иметь возможность манипулировать очередями по приоритетам так же, как мы манипулируем другими типами данных? Подобного типа вопросы служили предметом обсуждения в главе 4. Программа 9.8 представляет обобщенный интерфейс для очередей по приоритетам равно как и для строк, которые обсуждались в разделе 4.8. Она

находит применение в ситуации, когда клиентская программа работает с ключами и ассоциированной с ними информацией и, будучи главным образом заинтересованной в операции доступа к информации, ассоциированной с ключом с наибольшим значением, она, тем не менее, может выполнять и другие многочисленные операции по обработке данных в объектах, о чем шла речь в начале главы. Все эти операции обращаются к конкретной очереди по приоритетам через дескрипторы (указатель на структуру, которая не имеет конкретного описания). Операция вставить возвращает дескриптор каждого объекта, добавляемого в очередь по приоритетам в клиентской профамме. Дескрипторы объектов отличаются от дескрипторов очередей по приоритетам. При такой организации клиентские протраммы берут на себя обязанность отслеживать дескрипторы, которые впоследствии они могут использовать для определения, какие объекты подвергались воздействию со стороны операций удалить и изменить приоритет, и над какими очередями по приоритетам должны быть выполнены все указанные операции.

Данная организация налагает ограничения как на клиентскую программу, так и на реализацию. Клиентская программа не может получить доступ к информации никаким другим способом, кроме как за счет использования этого интерфейса. На нее возлагается ответственность за правильное использование дескрипторов: например, в реализации не существует сколь-нибудь подходящего способа проверки с целью выявления недопустимости такого действия, как использование клиентской программой дескриптора удаленного элемента. С другой стороны, реализация не может свободно перемещаться по информации, поскольку у клиентских программ имеются дескрипторы, которые они могут использовать на более поздних стадиях. Этот момент станет более понятным, когда мы приступим к исследованию деталей реализации. Как обычно, какой бы уровень детализации ни был бы выбран в наших реализациях, абстрактный интерфейс, такой как программа 9.8, представляет собой полезную отправную точку для нахождения компромисса между потребностями приложений и потребностями реализаций.

Прямолинейные реализации базовых операций над очередями по приоритетам, которые даны в программе 9.9, используют неупорядоченные представления данных в виде двухсвязных списков. Этот программный код иллюстрирует природу интерфейса; очень несложно построить другие, столь же бесхитростные реализации, используя другие элементарные представления.

Программа 9.8. Полный АТД очереди по приоритетам

Данный интерфейс для АТД очереди по приоритетам дает клиентским программам возможность удалять элементы и менять приоритеты (с использованием дескрипторов, предлагаемых программной реализацией), а также выполнять слияние очередей.

teB4>late <class Item> class PQ

private:

Прохзаммный код, зависящий от реализации public:

Определение дескриптора в зависимости от реализации PQ(int);

int empty О const;