Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
Завершение пирамидальной сортировки
Итак, массив упорядочен в виде сортирующего дерева. Что дальше? Удаление элементов по одному по-прежнему означает, что их нужно поместить куда-либо в отсортированном порядке, предположительно, в какой-нибудь вспомогательный массив. Так ли это? Немного подумаем. Если мы удаляем наибольший элемент, размер сортирующего дерева уменьшается на единицу, а в конце массива остается место для только что удаленного элемента. Фактически, алгоритм удаления элемента из сортирующего дерева требует, чтобы самый нижний, крайний справа узел копировался в позицию корневого узла, прежде чем к нему будет применена операция просачивания. Поэтому нужно всего лишь поменять местами корневой узел и самый нижний крайний справа узел, уменьшить значение счетчика количества элементов сортирующего дерева, а затем применить алгоритм просачивания.
Этот процесс нужно продолжать до тех пор, пока элементы в сортирующем дереве не иссякнут. В результате мы получаем элементы исходного массива, но теперь они оказываются отсортированными.
Полный код подпрограммы пирамидальной сортировки, реализованной так же, как были реализованы все процедуры сортировки в главе 5, приведен листинге 9.8.
Листинг 9.8. Алгоритм пирамидальной сортировки
procedure HSTrickleDown( aList : PPointerList; aFromInx : integer;
aCount : integer; aCompare : TtdCompareFunc );
var
Item : pointer;
ChildInx : integer;
ParentInx: integer;
begin
{вначале необходимо выполнить простую операцию просачивания, постоянно заменяя родительский узел его большим дочерним элементом, пока не будет достигнут нижний уровень сортирующего дерева}
Item := aList^[aFromInx];
ChildInx := (aFromInx * 2) + 1;
while (ChildInx < aCount) do
begin
if (suce(ChildInx) < aCount) and
(aCompare(aList^[ChildInx], aList^[suce(ChildInx)]) < 0) then
inc(ChildInx);
aList^[aFromInx] := aList^[ChildInx];
aFromInx := ChildInx;
ChildInx := (aFromInx * 2) + 1;
end;
{теперь из позиции, в которой был прекращен предыдущий процесс, необходимо выполнить операцию пузырькового подъема}
ParentInx := (aFromInx - 1) div 2;
while (aFromInx > 0) and (aCompare (Item, aList^[ParentInx] ) > 0) do
begin
aList^[aFromInx] := aList^[ParentInx];
aFromInx := ParentInx;
ParentInx := (aFromInx - 1) div 2;
end;
{сохранить элемент в той позиции, где был прекращен процесс пузырькового подъема}
aList^[aFromInx] := Item;
end;
procedure HSTrickleDownStd( aList : PPointerList;
aFromInx : integer;
aCount : integer;
aCompare : TtdCompareFunc );
var
Item : pointer;
ChildInx : integer;
begin
Item := aList^[aFromInx];
ChildInx := (aFromInx * 2) + 1;
while (ChildInx < aCount) do
begin
if (succ(ChildInx) < aCount) and
(aCompare(aList^[ChildInx], aList^[succ(ChildInx)]) < 0) then
inc(ChildInx);
if aCompare(Item, aList^[ChildInx]) >= 0 then
Break;
aList^[aFromInx] := aList^[ChildInx];
aFromInx := ChildInx;
ChildInx := (aFromInx * 2) + 1;
end;
aList^[aFromInx] := Item;
end;
procedure TDHeapSort( aList : TList; aFirst : integer;
aLast : integer; aCompare : TtdCompareFunc );
var
ItemCount : integer;
Inx : integer;
Temp : pointer;
begin
TDValidateListRange(aList, aFirst, aLast, 'TDHeapSort');
{преобразовать список за счет применения алгоритма пирамидальной сортировки Флойда}
ItemCount := aLast - aFirst + 1;
for Inx := pred( ItemCount div 2) downto 0 do
HSTrickleDownStd(@aList.List^[aFirst], Inx, ItemCount, aCompare);
{удаление элементов из сортирующего дерева по одному, с помещением их в конец массива}
for Inx := pred( ItemCount) downto 0 do
begin
Temp := aList.List^[aFirst];
aList.List^[aFirst] := aList.List^[aFirst+Inx];
aList.List^ [aFirst+Inx] :=Temp;
HSTrickleDown(@aList.List^[aFirst], 0, Inx, aCompare);
end;
end;
Обратите внимание, что на первом этапе, при создании сортирующего дерева из массива, мы использовали стандартный алгоритм просачивания (алгоритм Флойда), но на втором этапе (при удалении наибольшего элемента из постоянно уменьшающегося сортирующего дерева) был применен оптимизированный алгоритм просачивания Флойда. На первом этапе мы ничего не знали о распределении элементов в массиве, поэтому имело смысл просто применить стандартный алгоритм просачивания - в конце концов, в целом алгоритм Флойда является операцией типа O(n). Однако на втором этапе мы знаем, что меняем местами наибольший элемент и один из наименьших элементов. Поэтому в целесообразно осуществить оптимизацию.
До сих пор не был пояснен один момент. Если в качестве очереди по приоритету используется сортирующее дерево, отсортированное выбором максимального элемента, извлечение элементов будет выполняться в обратном порядке - начиная с наибольшего и заканчивая наименьшим. Однако если сортирующее дерево, отсортированная выбором максимального элемента, используется для пирамидальной сортировки, элементы будут отсортированы в порядке возрастания, а не в обратном порядке. При использовании кучи, отсортированной выбором минимального элемента, элементы будут удаляться в порядке возрастания, но пирамидальная сортировка будет выполняться в порядке убывания.
Важность алгоритма пирамидальной сортировки обусловлена целым рядом причин. Во-первых, время его выполнения определяется отношением O(n log(n)), следовательно, он работает достаточно быстро. Во-вторых, пирамидальная сортировка не имеет худшего случая. Сравним ее с быстрой сортировкой. В общем случае, как правило, быстрая сортировка выполняется быстрее пирамидальной (для выполнения пирамидальной сортировки потребуется выполнение большего количества операций сравнения, чем для быстрой сортировки, а внутренний цикл пирамидальной сортировки длится дольше, чем цикл быстрой сортировки). Но при выполнении быстрой сортировки возможны случаи, когда все ее преимущества сводятся буквально на нет, делая ее чрезвычайно медленной. (В худшем случае время выполнения этого алгоритма может определяться отношением O(n(^2^)), если только не будут приняты определенные меры по оптимизации алгоритма.) Если же сравнить пирамидальную сортировку с сортировкой слиянием, то мы видим, что эта сортировка выполняется на месте и не требует большого дополнительного объема памяти, как имеет место при выполнении сортировки слиянием. В заключение приходится признать, что алгоритм пирамидальной сортировки не очень устойчив.
Исходный код процедуры TDHeapSort и вспомогательных процедур можно найти на web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDSorts.pas.
Расширение очереди по приоритету
Сделав небольшое отступление для ознакомления с пирамидальной сортировкой, пора вернуться к очередям по приоритету и рассмотреть задачу расширения реализованной нами структуры данных.
Мы разработали структуру данных, позволяющую выполнять две основные операции: постановку в очередь, обеспечивающую добавление элемента в структуру, и исключение из очереди, которая возвращает элемент структуры с наивысшим приоритетом (попутно мы рассмотрели определение приоритета за счет использования внешней функции сравнения). Полученную структуру мы назвали очередью по приоритету.
Однако структуры операционных систем, такие как очереди по приоритету потоков или очереди на печать, позволяют выполнять еще две операции: удалять элемент из очереди и возвращать его, независимо от позиции в очереди (элемент не обязательно должен быть наибольшим), а также изменять приоритет любого элемента в очереди.
При работе с очередью на печать операция удаления позволяет отменять задание на печать документа, печать которого больше не требуется, или удалять печатное задание из одной очереди и включать его в другую (например, если принтер, связанный с первой очередью, занят печатью крупного отчета). При работе с очередью по приоритету потоков можно временно повысить приоритет потока для повышения вероятности возобновления выполнения, когда операционная система в следующий раз решит изменить очередность обработки потоков.
На первый взгляд, реализация этих операций за счет использования сортирующего дерева может показаться затруднительной. Однако рассмотрим проблему подробнее. Классу очереди по приоритету нужно было бы передать ссылку на элемент, расположенный где-то в очереди, чтобы его можно было удалить или изменить его приоритет. Как найти элемент в очереди? Это один из тех случаев, когда "свободная" сортировка сортирующего дерева работает против нас. Единственным возможным методом поиска на этом этапе кажется последовательный поиск, но он выполняется достаточно медленно. После того как элемент найден, мы должны либо удалить его, либо изменить его приоритет, а затем восстановить полноту или пирамидальность сортирующего дерева, либо же оба свойства.
Восстановление свойства пирамидальное
Вторую проблему (восстановление свойства пирамидальности) проще решить, чем первую (отыскание элемента, который нужно удалить или изменить его приоритет). Поэтому вначале рассмотрим именно ее.
Чтобы удалить произвольный элемент из сортирующего дерева, его нужно было бы поменять местами с последним элементом и уменьшить размер сортирующего дерева. На этом этапе появляется элемент, который может нарушить свойство пирамидальности.
Для изменения приоритета произвольного элемента следует просто внести изменение, в результате чего элемент может также нарушить свойство пирамидальности.
