Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Роберт Флойд (Robert Floyd) обратил внимание, что первый шаг операции исключения из очереди требует удаления элемента с наивысшим приоритетом и замены его одним из наименьших элементов сортирующего дерева. Этот элемент не обязательно должен быть наименьшим, но в процессе применения алгоритма просачивания он наверняка будет перемещен на один из нижних уровней дерева. Иначе говоря, большинство операций сравнения родительского элемента с его большим дочерним элементом, выполняемое в ходе процесса просачивания, вероятно, лишено особого смысла, поскольку результат сравнения заведомо известен: родительский элемент будет меньше своего большего дочернего элемента. Поэтом
Флойд предложил следующее: при выполнении процесса просачивания полностью отказаться от сравнений родительского
Описанная оптимизация приводит к уменьшению количества сравнений, выполняемых во время операции исключения из очереди, примерно в два раза. Если сравнения требуют значительных затрат времени (например, при сравнении строк), эта оптимизация себя оправдывает. Ее применение оправдано также и в нашей реализации очереди по приоритету, в которой мы используем функцию сравнения, а не простое сравнение целых чисел.
Листинг 9.7: Оптимизированная операция просачивания
procedure TtdPriorityQueue.pqTrickleDown;
var
FromInx : integer;
ChildInx : integer;
MaxInx : integer;
Item : pointer;
begin
FromInx := 0;
Item := FList.List^[0];
MaxInx := pred(FList.Count);
{выполнять обмен местами анализируемого элемента и его большего дочернего элемента до тех пор, пока у него не окажется ни одного дочернего элемента}
{Примечание: дочерние элементы родительского узла n располагаются в позициях 2n+1 и 2n+2}
ChildInx := (FromInx * 2) + 1;
{до тех пор, пока существует по меньшей мере левый дочерний элемент...}
while (ChildInx <= MaxInx) do
begin
{если при этом существует также правый дочерний элемент, необходимо вычислять индекс большего дочернего элемента}
if (succ(ChildInx) <= MaxInx) and
(FCompare(FList.List^[ChildInx], FList.List^[succ(ChildInx)]) < 0) then
inc(ChildInx);
{переместить больший дочерний элемент вверх, а данный элемент вниз по дереву и повторить процесс}
FList.List^[FromInx] := FList.List^[ChildInx];
FromInx := ChildInx;
ChildInx := (FromInx * 2) + 1;
end;
{сохранить элемент в той позиции, в которой процесс был прекращен}
FList.List^ [ FromInx ] := Item;
{теперь необходимо выполнить пузырьковый подъем этого элемента вверх по дереву}
pqBubbleUp(FromInx);
end;
Исходный код класса TtdPriorityQueue можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDPriQue.pas.
Пирамидальная сортировка
После того, как мы реализовали очередь по приоритету в виде сортирующего дерева, можно утверждать, что такое дерево можно использовать как алгоритм сортировки: одновременно добавлять в сортирующее дерево ряд элементов, а затем выбирать их по одному в требуемом порядке. (Обратите внимание, что в случае применения описанного метода элементы выбираются в обратном порядке. Т.е. вначале выбирается наибольший элемент. Однако если использовать обратный метод сравнения, элементы можно извлекать в порядке их возрастания.)
Не удивительно, что алгоритм сортировки с помощью сортирующего дерева называется пирамидальной сортировкой (heapsort). Если припоминаете, в главе 5 рассмотрение этого метода сортировки было отложено до приобретения необходимых теоретических сведений.
Только что названный алгоритм состоит в следующем: предположим, что у нас имеется очередь по приоритету, реализованная в виде сортирующего
дерева с выбором минимального элемента. Мы добавляем в него все элементы, а затем удаляем их по одному. Если бы вначале в структуре TList хранились неотсортированные элементы, применение этого алгоритма означало бы, что все элементы копировались бы из одной структуры TList в другую, а затем обратно. Намного более предпочтительным было бы применение сортировки по месту, при которой не нужно было бы копировать элементы из одного массива в другой. Иначе говоря, нельзя ли преобразовать существующий массив в сортирующее дерево, применив к нему свойство пирамидальности?Алгоритм Флойда
Роберт Флойд разработал такой достаточно интересный алгоритм, при котором время генерирования сортирующего дерева подчиняется отношению O(n), что значительно эффективнее алгоритма типа O(n log(n)) добавления элементов по одному в отдельное сортирующее дерево.
Алгоритм Флойда работает следующим образом. Процесс начинается с родительского узла самого правого дочернего узла (т.е. узла, расположенного в крайней правой позиции последнего уровня сортирующего дерева). Применим к этому родительскому узлу алгоритм просачивания. Выберем узел, расположенный на этом же уровне слева от родительского узла (конечно, он тоже будет родительским). Снова применим алгоритм просачивания. Продолжим перемещение влево, применяя алгоритм просачивания, пока не останется узлов для обработки. Перейдем к крайнему справа узлу следующего уровня. Продолжим этот же процесс перемещения справа налево, переходя от уровня к уровню, пока не будет достигнут корневой узел. С этого момента массив упорядочен в виде сортирующего дерева.
Чтобы доказать справедливость отношения O(n), предположим, что сортирующее дерево содержит 31 элемент (это сортирующее дерево будет иметь 5 заполненных уровней). На первом этапе нужно было бы выполнить обработку всех узлов четвертого уровня. Таких узлов восемь и для каждого из них потребовалось бы не более одной операции перемещения на более низкий уровень - всего таких операций требовалось бы не более восьми. На следующем этапе нужно было бы сформировать сортирующие мини-деревья на 3 уровне. Таких сортирующих деревьев четыре и для каждого требовалось бы не более двух операций понижения уровня (всего восемь). На следующем шаге потребовалось бы образовать сортирующие деревья на 2 уровне: существует три узла, которые могли бы требовать обработки, для каждого из которых может требоваться не более трех операций перемещения на более низкий уровень. Таким образом, для узлов этого уровня может потребоваться выполнение не более шести операций. Для образования сортирующего дерева на последнем шаге требуется максимум четыре операции понижения уровня. Таким образом, всего для формирования сортирующего дерева требовалось бы выполнение не более 26 операций перемещения на более низкий уровень -меньше исходного количества узлов. Если применить эти же рассуждения к сортирующему дереву с 2(^n^) - 1 узлами, выяснится, что для создания сортирующего дерева требуется не более 2(^n^) - n - 1 операций перемещения на более низкий уровень. Отсюда следует вывод о справедливости первоначального утверждения, что алгоритм Флойда является операцией типа O(n).
Завершение пирамидальной сортировки
Итак, массив упорядочен в виде сортирующего дерева. Что дальше? Удаление элементов по одному по-прежнему означает, что их нужно поместить куда-либо в отсортированном порядке, предположительно, в какой-нибудь вспомогательный массив. Так ли это? Немного подумаем. Если мы удаляем наибольший элемент, размер сортирующего дерева уменьшается на единицу, а в конце массива остается место для только что удаленного элемента. Фактически, алгоритм удаления элемента из сортирующего дерева требует, чтобы самый нижний, крайний справа узел копировался в позицию корневого узла, прежде чем к нему будет применена операция просачивания. Поэтому нужно всего лишь поменять местами корневой узел и самый нижний крайний справа узел, уменьшить значение счетчика количества элементов сортирующего дерева, а затем применить алгоритм просачивания.