Код интерфейса результирующей очереди по приоритету, в которой используется сортирующее дерево и которая реализована при помощи структуры TList, приведен в листинге 9.3.

Листинг 9.3. Интерфейс класса TtdPriorityQueue

type TtdPriorityQueue = class private FCompare : TtdCompareFunc;
FDispose : TtdDisposeProc;
FList : TList;
FName : TtdNameString;
protected
function pqGetCount : integer;
procedure pqError (aErrorCode : integer;
const aMethodName : TtdNameString) ;
procedure pqBubbleUp(aFromInx : integer);
procedure pqTrickleDown;
procedure pqTrickleDownStd;
public
constructor Create (aCompare : TtdCompareFunc;
aDispose : TtdDisposeProc ) ; destructor Destroy;
override; procedure Clear;
function Dequeue : pointers-procedure Enqueue(altern : pointer);
function Examine : pointers-function IsEmpty : boolean;
property Count : integer read pqGetCount;
property Name : TtdNameString read FName write FName;
end;

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

Листинг 9.4. Конструктор и деструктор очереди по приоритету

constructor TtdPriorityQueue. Create (aCompare : TtdCompareFunc;
aDispose : TtdDisposeProc);
begin inherited Create;
if not Assigned (aCompare) then pqError(tdePriQueueNoCompare, 1 Create1);
FCompare := aCompare;
FDispose :=aDispose;
FList := TList.Create;
end;
destructor TtdPriorityQueue.Destroy;
begin
Clear;
FList.Free;
inherited Destroy;
end;

Код реализации алгоритма вставки и процедуры, выполняющей реальную операцию пузырькового подъема, показан в листинге 9.5. Операция вставки реализована так, чтобы гарантировать размещение наибольшего элемента в корневом узле. Этот тип очереди по приоритету обычно называют пирамидальной сортировкой выбором максимального элемента (max-heap). Если изменить процедуру сравнения так, чтобы она возвращала отрицательное число, если первый элемент больше второго, в корневом узле очереди по приоритету будет располагаться наименьший элемент. Такая сортировка называется пирамидальной сортировкой выбором наименьшего элемента (min-heap).

Листинг 9.5. Вставка в TtdPriorityQueue: постановка в очередь

procedure TtdPriorityQueue.pqBubbleUp(aFromInx : integer); var
ParentInx : integer;
Item : pointer;
begin
Item := FList .ListA [aFromlnx];
{если анализируемый элемент больше своего родительского элемента, необходимо поменять его местами с родительским элементом и продолжить процесс из новой позиции элемента)
{Примечание: родительский узел узла, имеющего индекс п, располагается в позиции (л-1)/2) Parent Inx := (aFromlnx - 1) div2;
{если данный элемент имеет родительский узел и больше родительского элемента...} while (aFromlnx > 0) and (FCompare (Item, FList.List* [Parent Inx ]) > 0) do begin
{необходимо переместить родительский элемент вниз по дереву) FList.ListА[aFromlnx] := FList.ListА[ParentInx]; aFromlnx : = ParentInx;
Parent Inx := (aFromlnx - 1) div2;
end;
{сохранить элемент в правильной пбзиции) FList.Listл[aFromlnx] := Item;
end;
procedure TtdPriorityQueue. Enqueue (altem : pointer);
begin
{добавить элемент в конец списка и выполнить его пузырьковый подъем на максимально возможный уровень) FList.Add(altem);
pqBubbleüp(pred(FList.Count));
end;

В листинге 9.6 приведен фрагмент кода, реализующий последнюю часть очереди по приоритету: алгоритм удаления и процедуру, которая выполняет операцию просачивания вниз.

Листинг 9.6. Удаление из TtdPriorityQueue: исключение из очереди

procedure TtdPriorityQueue.pqTrickleDownStd;
var
Fromlnx : integer;
Childlnx : integer;
Maxlnx : integer;
Item : pointer;
begin
Fromlnx := 0;
Item := FList.ListA[0];
Maxlnx := FList.Count - 1;
{если анализируемый элемент меньше одного из его дочерних элементов, нужно поменять его местами с большим дочерним элементом и продолжить процесс из новой позиции)
{Примечание: дочерние узлы родительского узла п располагаются в позициях 2п+1 и 2п+2) Childlnx := (Fromlnx * 2) + 1;

{если существует по меньшей мере левый дочерний узел...} while (Childlnx <= Maxlnx) do begin {если существует также и правый дочерний узел, необходимо вычислить индекс большего дочернего узла) if (succ(Childlnx) <= Maxlnx) and

(FCompare(FList.ListA[Childlnx], FList.List"4 [succ(Childlnx) ]) < 0) then inc(Childlnx);
{если данный элемент больше или равен большему дочернему элементу, задача выполнена}
if (FCompare(Item, FList .Listл [Childlnx]) >= 0) then Break;
{в противном случае больший дочерний элемент нужно переместить верх по дереву, а сам элемент - вниз по дереву, а затем повторить процесс) FList.ListA[Fromlnx] := FList.ListA[Childlnx]; Fromlnx := Childlnx;
Childlnx := (Fromlnx * 2) + 1;
end;
{сохранить элемент в правильной позиции) FList.ListА[Fromlnx] := Item;
end;
function TtdPriorityQueue. Dequeue : pointer;
begin
{проверить наличие элемента для его исключения из очереди) if (FList. Count = 0) then
pqError(tdeQueuelsEmpty, 'Dequeue1); {вернуть элемент, расположенный в корневом узле) Result := FList.ListA[0];

{если очередь содержала только один элемент, теперь она пуста) if (FList.Count = 1) then FList.Count := 0

{если очередь содержала два элемента, достаточно заменить корневой узел единственным оставшимся дочерним узлом; очевидно, что при этом свойство пирамидальности сохраняется) else if (FList.Count = 2) then begin
FList.ListA[0] : = FList.ListA[1];
FList.Count := 1; end
{в противном случае больший дочерний элемент нужно переместить верх по дереву, а сам элемент - вниз по дереву, а затем повторить процесс) else begin
{заменить корневой узел дочерним узлом, расположенным в нижней правой позиции, уменьшить размер списка, и, наконец, выполнить просачивание корневого элемента вниз на максимальную глубину) FList.ListA[0] := FList.Last;
FList.Count := FList.Count - 1; pqTrickleDownStd;
end;
end;

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

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

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

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

Листинг 9.7: Оптимизированная операция просачивания

procedure TtdPriorityQueue.pqTrickleDown;
var
Fromlnx : integer;
Childlnx : integer;
Maxlnx : integer;
Item : pointers-begin
Fromlnx := 0;
Item : = FList.ListA[ 0 ];
Maxlnx : = pred(FList.Count);
{выполнять обмен местами анализируемого элемента и его большего дочернего элемента до тех пор, пока у него не окажется ни одного дочернего элемента)
{Примечание: дочерние элементы родительского узла п располагаются в позициях 2п+1 и2л+2)
Childlnx := (Fromlnx * 2) + 1;

{до тех пор, пока существует по меньшей мере левый дочерний элемент...) while (Childlnx <= Maxlnx) do begin {если при этом существует также правый дочерний элемент, необходимо вычислять индекс большего дочернего элемента) if (succ(Childlnx) <= Maxlnx) and

(FCompare(FList.ListA[Childlnx], FList.ListA[succ(ChildInx)]) < 0) then inc(Childlnx);
{переместить больший дочерний элемент вверх, а данный элемент вниз по дереву и повторить процесс) FList.ListА[Fromlnx] := FList.ListА[Childlnx]; Fromlnx := Childlnx;
Childlnx := (Fromlnx * 2) + 1;
end;
{сохранить элемент в той позиции, в которой процесс был прекращен} FList. ListА [ Fromlnx ] : = Item;
{теперь необходимо выполнить пузырьковый подъем этого элемента вверх по дереву} pqBubbleUp(Fromlnx);
end;

Исходный код класса TtdPriorityQueue можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDPriQue.pas.

Удаление из сортирующего дерева || Оглавление || Пирамидальная сортировка


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



Новости за месяц

  • Май
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс