Лекции - Структуры и алгоритмы компьютерной обработки данных / 6.Пирамидальная сортировка и очередь с приоритетом
.docПирамидальная сортировка
Массив [1.. N] можно рассматривать как двоичное дерево. У элемента, расположенного в ячейке с номером i, левый ребенок будет в ячейке с номером 2i, правый – в ячейке с номером 2i+1. Обратно, у элемента i родитель находится в ячейке i div 2.
Пирамида (куча, heap)
Дерево называется пирамидой, если ключ любого элемента не меньше, чем ключи его детей. Это свойство называется основным свойством пирамиды и может быть записано следующей формулой: Ai/2 ≥ Ai
Пример пирамиды:
Добавление элемента в корень пирамиды
Рассмотрим добавление в корень существующей пирамиды нового элемента. Этот элемент нарушает основное свойство пирамиды. Он должен быть сдвинут вниз по дереву на свое место. Напишем процедуру ShiftDown, восстанавливающую основное свойство. Процедура сравнивает ключ узла с ключами его детей, ставит в корень элемент с наибольшим ключом и рекурсивно делает то же самое в поддереве, из которого взят этот элемент. Если максимальный элемент уже стоит в корне, то выполнение процедуры завершается.
Процедура ShiftDown
A[1..N] – пирамида, Size – размер пирамиды (Size ≤ N)
Procedure ShiftDown(var A:DataSet; k:integer);
Var max: integer;
t: data;
begin
if (2*k<=Size) and (A[k].key<=A[2*k].key)
then max:=2*k else max:=k;
if (2*k+1<=Size) and (A[2*k+1].key>=A[max].key)
then max:=2*k+1;
if k<>max then
begin
t:=A[k]; A[k]:=A[max]; A[max]:=t;
ShiftDown(A,max);
end;
end;
Построение пирамиды в исходном массиве
Сложность процедуры определяется высотой дерева Ө(log N).
Для построения пирамиды из исходного массива можно применить процедуру ко всем элементам, начиная с последних, в обратном порядке.
Вершины с номерами [N/2]+1 … N - листья, и для них выполнено основное свойство. Для остальных вершин в порядке убывания индексов выполним процедуру ShiftDown. Сложность построения пирамиды Ө(N).
Пирамидальная сортировка
Для сортировки сначала строим пирамиду, при этом максимальный элемент оказывается на вершине. Далее ставим его в конец массива, уменьшаем размер кучи и восстанавливаем основное свойство.
Фрагмент процедуры:
for i:=length(A) downto 2 do
begin
t:=A[1]; A[1]:=A[i]; A[i]:=t;
size:=size-1;
ShiftDown(A,1)
end;
Сложность в худшем случае Ө(n log n). Алгоритм пирамидальной сортировки неустойчивый, не требует дополнительной памяти. Однако быстрая сортировка на практике быстрее в среднем на 40%.
Очереди с приоритетами
Очередь с приоритетами – структура данных, допускающая следующие операции:
-
Insert (s, x) – добавляет к множеству s элемент х;
-
Maximum (s) – возвращает элемент множества s с наибольшим ключом;
-
DeleteMax(s) - удаляет элемент с наибольшим ключом из множества s.
Примеры использования: выполнение заданий операционной системой, составление графика работ.
Реализация очереди с приоритетами пирамидой
Maximum (s):
максимальный элемент – в корне.
Ө(1)
DeleteMax(s):
max:=A[1]; A[1]:=A[size]; size:=size-1;
ShiftDown(A,1);
Ө(log N)
Добавление в очередь с приоритетами
Добавим элемент в конец кучи (как лист), а затем поднимем его до нужного места. Ө(log n)
Procedure insert(var A:DataSet; x:data);
Var i: integer;
begin
size := size+1;
i := size;
while (i>1) and (A[i div 2].key < x.key) do
begin
A[i] := A[i div 2];
i := i div 2;
end;
A[i] := x;
end;