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

if (FCompare(Item, FList.List^[ChildInx]) >= 0) then

Break;

{в противном случае больший дочерний элемент нужно переместить верх по дереву, а сам элемент - вниз по дереву, а затем повторить процесс}

FList.List^[FromInx] := FList.List^[ChildInx];

FromInx := ChildInx;

ChildInx := (FromInx * 2) + 1;

end;

{сохранить элемент в правильной позиции}

FList.List^[FromInx] := Item;

end;

function TtdPriorityQueue.Dequeue : pointer;

begin

{проверить наличие элемента для его исключения из очереди}

if (FList.Count = 0) then

pqError(tdeQueueIsEmpty, 'Dequeue');

{вернуть элемент, расположенный в корневом узле}

Result := FList.List^[0];

{если очередь содержала только один элемент, теперь она пуста}

if (FList.Count = 1) then

FList.Count := 0

{если очередь содержала два элемента, достаточно заменить корневой узел единственным оставшимся дочерним узлом; очевидно, что при этом свойство пирамидальности сохраняется}

else

if (FList.Count = 2) then begin

FList.List^[0] := FList.List^[1];

FList.Count := 1;

end

{в противном случае больший дочерний элемент нужно переместить верх по дереву, а сам элемент - вниз по дереву, а затем повторить процесс}

else begin

{заменить корневой узел дочерним узлом, расположенным в нижней правой позиции, уменьшить размер списка, и, наконец, выполнить просачивание корневого элемента вниз на максимальную глубину}

FList.List^[0] := FList.Last;

FList.Count := FList.Count - 1;

pqTrickleDownStd;

end;

end;

Обратите внимание, что на каждом этапе выполнения алгоритма просачивания в процессе перемещения элементов вниз по куче выполняется не более двух сравнений: сравнение двух дочерних элементов с целью определения большего из них и сравнение большего дочернего элемента с родительским элементом для выяснения того, нужно ли их менять местами. По сравнению с операцией пузырькового подъема, когда при подъеме в рамках сортирующего дерева на каждом уровне выполняется только одно сравнение, этот алгоритм выглядит несколько излишне трудоемким. Нельзя ли каким-то образом улучшить ситуацию?

Роберт Флойд (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).