Структуры данных и алгоритмы (1021739), страница 62
Текст из файла (страница 62)
Таким образом, общее время выполнения алгоритма имеет порядокО(п logn), если, конечно, используется подходящая структура данных.Структура данных частично упорядоченных деревьев из раздела 4.11 хорошо подходит для данного алгоритма. Напомним, что частично упорядоченное дерево можнопредставить в виде кучи — массива А, чьи элементы подчиняются неравенствамA[i].key < A[2*i].key и A[i].key < A[2*i + l].key.
Если интерпретировать элементы синдексами 2i и 2i + 1 как "сыновей" элемента с индексом i, тогда массив А формирует сбалансированное двоичное дерево, в котором значения ключей родителей никогдане превосходят значения ключей сыновей.В разделе 4.11 было показано, что частично упорядоченное дерево поддерживаетоператоры INSERT и DELETEMIN с временем выполнения O(logn). Но на частичноупорядоченном дереве нельзя реализовать общий оператор DELETE с временем выполнения O(logn) (всегда найдется отдельный элемент, требующий линейного времени удаления в самом худшем случае). В связи с этим отметим, что в листинге 8.9удаляются только элементы, имеющие минимальные значения ключей.
Поэтомустроки (4) и (6) можно объединить одним оператором DELETEMIN, который будетвозвращать элемент у. Таким образом, используя структуру данных частично упорядоченного дерева из раздела 4.11, можно выполнить абстрактный алгоритм сортировки за время О(п logn).Сделаем еще одно изменение в алгоритме листинга 8.9, чтобы избежать печатиудаляемых элементов. Заметим, что множество S всегда хранится в виде кучи вверхней части массива А, даже когда содержит только i элементов (i < п). Для частично упорядоченного дерева наименьший элемент всегда хранится в ячейке А[1].Элементы, уже удаленные из множества S, можно было бы хранить в ячейках1Свое название этот алгоритм получил вследствие того, что применяемое здесь частичноупорядоченное сортирующее дерево имеет вид "пирамиды". Отметим также, что в русском издании книги [3] этот метод сортировки назван "сортдеревом", т.е.
упорядочиванием посредством сортирующего дерева. — Прим. ред.244ГЛАВА 8. СОРТИРОВКАA[i + 1], ..., A[n], сортированными в обратном порядке, т.е. так, чтобы выполнялись1неравенства А[1 + 1] > A[i + 2] > ... >A[ri]. Поскольку элемент Л[1] является наименьшим среди элементов А[1], ..., A[i], то для повышения эффективности оператораDELETEMIN можно просто поменять местами элементы А[1] и A[i].
Поскольку новыйэлемент A[i] (т.е. старый А[1]) не меньше, чем A[i + 1] (элемент A[i + 1] был удалениз множества S на предыдущем шаге как наименьший), то получим последовательность A[i], ..., А[п], отсортированными в убывающем порядке. Теперь надо занятьсяразмещением элементов.А[1], ..., A[i - 1].Поскольку новый элемент А[1] (старый элемент A[i\) нарушает структуру частичноупорядоченного дерева, его надо "протолкнуть" вниз по ветвям дерева, как это делаетсяв процедуре DELETEMIN листинга 4.13. Здесь для этих целей мы используем процедуру pushdown (протолкнуть вниз), оперирующую с массивом А, определенным вне этойпроцедуры. Код процедуры pushdown приведен в листинге 8.10.
С помощью последовательности перестановок данная процедура "проталкивает" элемент A[first] вниз по дереву до нужной позиции. Чтобы восстановить частично упорядоченное дерево в случаенашего алгоритма сортировки, надо вызвать процедуру pushdown для first — 1.••;f,Y' •;•.';>•../•••.•..'.•:''••••.':..'•:'.:- : ::.'.':'•:•••.-Листинг 8.10. Процедура pushdown. •<;••..;•-.......:... •••••.. -..,,••,•• •/•:<::t:::procedure pushdown ( first, last: integer );{ Элементы A[first], ....
A[last] составляют частичноупорядоченное дерево за исключением, возможно, элементаAlfirst] и его сыновей. Процедура pushdownвосстанавливает частично упорядоченное дерево }varг: integer; { указывает текущую позицию A[first] }beginr:= first; { инициализация }•while г <= last div 2 doif last = 2*r then begin{ элемент в позиции г имеет одного сынав позиции 2*г }if A [ r ] .
k e y > A[2*r].key thenswap(A[r], A [ 2 * r ] ) ir:= last { досрочный выход из цикла while }endelse { элемент в позиции г имеет двух сыновейв позициях 2*г и 2*г + 1 }if A[r].key > A [ 2 * r ] . k e y andA [ 2 * r ] . k e y <= A[2*r + 1].key then begin{ перестановка элемента в позиции гс левым сыном }swap(A[r], А [ 2 * г ] ) ;r:= 2*rend(.else if A [ r ] .key > A[2*r + l].Jcey,andA[2*r + 1].key < A[2*r].^ey then begin{ перестановка элемента в позиции гс правым сыном }1В таком случае в конце выполнения алгоритма сортировки мы получим массив А, содержащий элементы, упорядоченные в обратном порядке. Если необходимо, чтобы в конце сортировки массив А содержал элементы в возрастающем порядке (начиная с наименьшего), то надопросто заменить оператор DELETEMIN на оператор DELETEMAX, а частично упорядоченноедерево организовать так, чтобы каждый родитель имел значение ключа не меньшее, чем у егосыновей.8.4.
ПИРАМИДАЛЬНАЯ СОРТИРОВКА245swap(A[r], A[2*r + 1]);r:= 2*r + 1endelse { элемент в позиции г не нарушает порядокв частично упорядоченном дереве }r:= last { выход из цикла while }.end; { pushdown }Вернемся к листингу 8.9 и займемся строками (4) - (6). Выбор минимальногоэлемента в строке (4) прост — это всегда элемент А[1]. Чтобы исключить операторпечати в строке (5), мы поменяли местами элементы А[1] иА[С\ в текущей куче. Удалить минимальный элемент из текущей кучи также легко: надо просто уменьшитьна единицу курсор i, указывающий на конец текущей кучи.
Затем надо вызвать процедуру pushdown(l, I - 1) для восстановления порядка в частично упорядоченном дереве кучи А[1], ..., A[i - 1].Вместо проверки в строке (3), не является ли множество S пустым, можно проверить значение курсора i, указывающего на конец текущей кучи. Теперь осталось рассмотреть способ выполнения операторов в строках (1), (2). Можно с самого начала поместить элементы списка L в массив А в произвольном порядке. Для создания первоначального частично упорядоченного дерева надо последовательно вызывать процедуруpushdown(j, п) для всех j = л/2, л/2 - 1, ..., 1. Легко видеть, что после вызова процедуры pushdown(j, n) порядок в ранее упорядоченной части строящегося дерева не нарушается, так как новый элемент, добавляемый в дерево, не вносит нового нарушения порядка, поскольку он только меняется местами со своим "меньшим" сыном.
Полныйкод процедуры heapsort (пирамидальная сортировка) показан в листинге 8.11.Листинг 8.11. Процедура пирамидальной сортировки»''::•:"•:•'*'.• < " " . . :'"-:•.:'•*'.:?'..:• . '•'•':•''..,:•'.'•'''••-"•":'...:.у.!..•.'.*;:,*•.procedure heapsort;{ Сортирует элементы массива Л[1], ..., Л[л]в убывающем порядке }var(1)(2)(3)(4)(5)i: integer; { курсор в массиве А }begin{ создание частично упорядоченного дерева }for i:= л div 2 downto 1 dopushdown(if n);for i: = n downto 2 do beginswap(A[l], A [ i ] ) ;{ удаление минимального элемента из кучи }pushdown(I, i - I){ восстановление частично упорядоченного дерева }endend; { heapsort }Анализ пирамидальной сортировкиСначала оценим время выполнения процедуры pushdown. Из листинга 8.10 видно,что тело цикла while (т.е. отдельная итерация этого цикла) выполняется за фиксированное время.
После каждой итерации переменная г по крайней мере вдвое увеличивает свое значение. Поэтому, учитывая, что начальное значение г равно first, после iитераций будем иметь г > first * 2'. Цикл while выполняется до тех пор, покаг > last/2. Это условие будет выполняться, если выполняется неравенствоfirst * 2' > last/2. Последнее неравенство можно переписать какi > log(last/first) - 1.246(8.8)«•ГЛАВА 8. СОРТИРОВКАСледовательно, число итераций цикл while в процедуре pushdown не превышаетlog(last/first).Поскольку first > 1 и last < n, то из (8.8) следует, что на каждый вызов процедуры pushdown в строках (2) и (5) листинга 8.11 затрачивалось время, по порядку небольшее, чем O(logn).
Очевидно, что цикл for строк (1), (2) выполняется п/2 раз. По1этому общее время выполнения этого цикла имеет порядок O(n logn). Цикл в строках (3) - (б) выполняется п - 1 раз. Следовательно, на выполнение всех перестановокв строке (4) тратится время порядка О(п), а на восстановление частично упорядоченного дерева (строка (5)) — О(п logn). Отсюда вытекает, что общее время выполненияцикла в строках (3) - (б) имеет порядок О(п logn) и такой же порядок времени выполнения всей процедуры heapsort.Несмотря на то что процедура heapsort имеет время выполнения порядкаО(п logn) в самом худшем случае, в среднем ее время несколько хуже, чем в быстрой сортировке, хотя и имеет тот же порядок. Пирамидальная сортировка интересна в теоретическом плане, поскольку это первый рассмотренный нами алгоритм, имеющий в самом худшем случае время выполнения О(п logn). В практических ситуациях этот алгоритм полезен тогда, когда надо не сортировать все пэлементов списка, а только отобрать k наименьших элементов, и при этом k значительно меньше п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
