Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

Флойд предложил следующее: при выполнении процесса просачивания полностью отказаться от сравнений родительского элемента с большими дочерними элементами и всегда менять местами родительский элемент и его больший дочерний элемент. Конечно, со временем мы достигнем нижнего уровня сортирующего дерева, и элемент может оказаться в неправильной позиции (другими словами, он может оказаться больше своего родительского элемента). Это не имеет значения, поскольку в этом случае мы просто воспользуемся операцией пузырькового подъема. Поскольку элемент, к которому было применено просачивание, был одним из наименьших в сортирующем дереве, весьма вероятно, что его придется поднимать не слишком высоко, если вообще придется.

Описанная оптимизация приводит к уменьшению количества сравнений, выполняемых во время операции исключения из очереди, примерно в два раза. Если сравнения требуют значительных затрат времени (например, при сравнении строк), эта оптимизация себя оправдывает. Ее применение оправдано также и в нашей реализации очереди по приоритету, в которой мы используем функцию сравнения, а не простое сравнение целых чисел.

Листинг 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).