Главная » Java, Структуры данных и алгоритмы » Пирамидальная сортировка

0

Как показано выше, реализация очереди с приоритетами с помощью пирамиды имеет то преимущество, что все методы выполняются в логарифмическом времени и даже быстрее. Следовательно, такая реализация удовлетворяет требованиям приложений, где требуется быстрое выполнение всех методов очереди с приоритетами. Поэтому еще раз рассмотрим схему сортировки PriorityQueueSort (п. 7Л.2), в которой для сортировки последовательности S используется очередь Р.

Если реализуется очередь с приоритетами с помощью пирамиды, то в первой стадии каждая из п операций insertltem займет 0(log к) времени, где к — количество элементов пирамиды на этот момент. Аналогично на второй стадии каждая из п операций removeMin будет выполняться за 0(log к) времени, где к — количество элементов пирамиды в текущий момент. Поскольку всегда к < п, каждая такая операция максимально занимает 0(log п) времени. Таким образом, каждая стадия требует 0(п log п) времени, соответственно, при использовании пирамидальной реализации весь алгоритм сортировки очереди с приоритетами будет выполняться за 0(п log п) времени. Такой алгоритм сортировки больше известен как пирамидальная сортировка (heap-sorting), а показатели его производительности приводятся в следующем утверждении.

Утверждение 7.2. Алгоритм пирамидальной сортировки сортирует последовательность S из п сравнимых элементов за O(nlogn) времени.

Из табл. 3.3 видно, что время выполнения 0(п log п) пирамидальной сортировки значительно меньше, чем время выполнения 0(п[18]) пузырьковой сортировки (раздел 5.4), сортировки методом выбора и сортировки методом ввода (п. 7.2.3).

Реализация внутренней пирамидальной сортировки

Если сортируемая последовательность Sреализована с помощью массива, можно ускорить пирамидальную сортировку и ограничить требования к занимаемой памяти некоторым постоянным фактором, использующим сегмент самой последовательности ?для хранения пирамиды, таким образом избежав применения внешней пирамидальной структуры данных. Этого можно добиться путем модификации алгоритма следующим путем.

часть 5 с индексами от /-1 до п-1 используем для хранения элементов последовательности. Таким образом, первые / элементов (/ = 0, …, /-1) обеспечивают векторное представление пирамиды (с модифицированной нумерацией уровней — от 0 вместо 1), при котором элемент уровня к больше или равен своим дочерним элементам уровня 2к +1 и 2к +2.

2.      На первой стадии алгоритма начнем с пустой пирамиды, и каждый раз на один шаг передвигаем границу между пирамидой и последовательностью слева направо. На шаге / (/ = 1, …, п) увеличиваем пирамиду, добавляя элемент в уровень /-1.

3.      На второй стадии алгоритма начнем с пустой последовательности, и каждый раз на один шаг передвигаем границу между пирамидой и последовательностью справа налево. На шаге / (/’ = 1, …, п) удаляем наибольший элемент из пирамиды и сохраняем его на уровне п – /.

Такая разновидность сортировки пирамиды называется внутренней сортировкой (sort in-place), поскольку в дополнение к самой последовательности используется одно и то же пространство. Вместо передачи элементов из последовательности и обратно производится их реорганизация. Сортировка этого типа представлена на рис. 7.8. В принципе можно говорить о внутренней сортировке, если при этом дополнительно к памяти, необходимой для самих сортируемых объектов, используется некоторый постоянный объем памяти.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии