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

Автор книги: Джулиан Бакнелл

сообщить о нарушении

Текущая страница: 24 (всего у книги 36 страниц)

Рисунок 8.10. Удаление узла, имеющего два внешних дочерних узла

Второй случай удаления – удаление узла, который имеет один реальный дочерний узел и один внешний дочерний узел. Предположим, что удаляемый узел является красным. Его единственный реальный дочерний узел будет черным. Можно удалить узел и заменить его единственным дочерним узлом. Это не приведет к нарушению правила 2, – в конечном счете, мы удаляем красный узел, – а правило 3 в данном случае не затрагивается, следовательно, дерево остается красно-черным. Этот случай представлен первым преобразованием на рис. 8.11.

Теперь предположим, что удаляемый узел является черным. Единственный дочерний узел может быть красным или черным. Предположим, что он красный. Правило 2 неизбежно нарушается, поскольку мы удаляем черный узел, а правило 3 может быть нарушено, так как новый родительский узел красного дочернего узла может также оказаться красным. Однако этот случай достаточно прост: нужно просто перекрасить красный дочерний узел в черный цвет при перемещении его вверх для замещения удаленного узла. В результате этого простого действия мы снова добиваемся выполнения правила 2, а правило 3 в данном случае не затрагивается. Дерево снова становится красно-черным. Тот случай представлен вторым преобразованием, показанным на рис. 8.11.

Однако случай, когда единственный дочерний узел является черным, сложнее третье преобразование (на рис. 8.11). Что ж, запомним о существовании этой проблемы и рассмотрим третий, он же и последний, случай удаления.

В действительности заключительный случай удаления из дерева бинарного поиска не отличается от двух уже рассмотренных, поскольку, если помните, мы меняем местами узел, который нужно было бы удалить, с наибольшим узлом из левого дочернего дерева, а затем удаляем этот второй узел вместо первого. Этот второй узел будет соответствовать либо первому, либо второму случаю удаления, поэтому две проблемы, решение которых мы отложили, придется решать раньше, чем мы полагали.

Рисунок 8.11.

Удаление узла, который имеет один внутренний и один внешний дочерний узел

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

Однако если удаляемый узел черный и имеет, по меньшей мере, один внешний дочерний узел, а другой дочерний узел либо черный, либо внешний, то мы сталкиваемся с двумя ранее описанными проблемами. Повышение ранга дочернего узла в результате удаления приводит к нарушению правила 2 (назовем этот узел нарушающим узлом). Эти случаи представлены последними преобразованиями, изображенными на рисунках 8.10 и 8.11.

Попытаемся свести оба случая к одному. Мы должны принимать во внимание родительский и братский узлы нарушающего узла и два дочерних узла братского узла (узлы-племянники). Обратите внимание, что можно принять наличие у братского узла двух дочерних узлов (т.е. считать, что братский узел не является внешним). Почему? Рассмотрим исходное дерево. Оно было красно-черным. Следовательно, все пути, проходящие через удаленный и родительский узлы, имели то же количество черных узлов, что и пути, проходящие через братский и родительский узлы. Поскольку мы предполагаем, что родительский узел черный, а удаленный узел и заменивший его дочерний узел также были черными, то и все пути, проходящие через братский узел, должны содержать, по меньшей мере, два черных узла. Отсюда следует, что, как минимум, братский узел является черным и имеет два черных дочерних узла.

Как бы там ни было, рассмотрим братский узел. Последующие рассуждения упростятся, если принять, что братский узел является черным. Если это не так, нужно перекрасить родительский узел в красный цвет, а братский – в черный, после чего повернуть родительский узел и повысить ранг братского узла. Результирующее дерево будет красно-черным, если не обращать внимания на исходный нарушающий узел, но в нем братский узел гарантированно является черным. Таким образом, в дальнейшем будем считать, что братский узел окрашен в черный цвет. (Обратите внимание, что если бы братский узел был красным, то его дочерние узлы должны были быть черными и, более того, чтобы правило 2 изначально выполнялось, они должны были бы иметь собственные дочерние узлы. Следовательно, это преобразование сохраняет существование братского узла с дочерними узлами и красно-черное состояние дерева.)

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

Рисунок 8.12. Балансировка после удаления: первый случай

Второй возможный случай – существование красного родительского узла и двух черных узлов-племянников. Этот случай даже проще предыдущего: нужно перекрасить родительский узел в черный цвет, а братский – в красный. Путь, проходящий через нарушающий узел, снова имеет требуемое количество черных узлов (тем самым удовлетворяя правило 2). Это же можно сказать и по поводу пути, проходящего через братский узел (правило 2 снова выполняется). Только что окрашенный в красный цвет узел имеет черный родительский узел, следовательно, правило 3 не нарушается. Стало быть, мы снова получаем красно-черное дерево. Этот случай показан на рис. 8.13.

Рисунок 8.13. Балансировка после удаления: второй случай

Теперь предположим, что противоположный по отношению к нарушающему узлу узел-племянник является красным. (Иначе говоря, если нарушающий узел -это левый дочерний узел родительского узла, речь идет о правом узле-племяннике, а если нарушающий узел – правый дочерний узел, речь идет о левом узле-племяннике.) Перекрасим этот узел-племянник в черный цвет. Окрасим братский узел в цвет родительского узла (первоначальный цвет родительского узла не имеет значения), а родительский узел – в черный цвет. Затем повернем родительский узел и повысим ранг братского узла. Тщательно проанализируем эту ситуацию, глядя на рис. 8.14. Вначале проверим выполнение правила 3: очевидно, что мы не ввели никаких новых красных узлов, следовательно, можно быть уверенным, что это правило выполняется. Теперь рассмотрим выполнение правила 2. Все пути, проходящие через нарушающий узел, содержат дополнительный черный узел, что ведет к устранению проблемы, возникшей в результате удаления исходного узла. Все пути, проходящие через дочерние деревья 5 и 6, также содержат то же количество черных узлов, что и ранее. Следовательно, во всех случаях правило 2 выполняется, и результирующее дерево снова является красно-черным.

Рисунок 8.14. Балансировка после удаления: третий случай

Теперь рассмотрим последний случай. Предположим, что противоположный узел-племянник окрашен в черный цвет, но второй узел этой же степени родства является красным. На этот раз нужно выполнить спаренный двусторонний поворот. Вначале мы окрашиваем узел-племянник в цвет родительского узла (как и в предыдущем случае, первоначальный цвет родительского узла значения не имеет), а затем перекрашиваем родительский узел в черный цвет. Далее мы поворачиваем братский узел, чтобы повысить ранг узла-племянника, а затем поворачиваем родительский узел, чтобы снова повысить ранг узла-племянника. Это преобразование показано на рис. 8.15. В любом случае это не ведет к непреднамеренному нарушению правила 3: мы не ввели никаких новых красных узлов. Теперь что касается правила 2 – все пути, проходящие через нарушающий узел, содержат один дополнительный черный узел, следовательно, ранее описанная проблема устранена. Все пути, проходящие через дочернее дерево 3, по-прежнему содержат одинаковое количество черных узлов. Аналогично, во всех путях, проходящих через дочерние деревья 4, 5 и 6, не был вставлен или удален какой-либо дополнительный черный узел, следовательно, правило 3 по-прежнему выполняется. Дерево снова оказывается красно-черным.

Если нарушающий узел удается переместить до позиции корневого узла, создается предельная ситуация. В этом случае нарушающий узел не имеет родительского узла и, следовательно, не может иметь братский узел. При этом нарушающий узел больше не представляет проблемы.

Конечно, все рассмотренные случаи имеют аналоги, представляющие их зеркальные отражения, но при этом анализ каждого из случаев удаления остается тем же. При написании кода подпрограммы удаления нужно будет убедиться, что мы правильно отразили как левые, так и правые варианты расположения узлов.

Рисунок 8.15. Балансировка после удаления: заключительный случай

Итак, мы рассмотрели все возможности. При этом использовались два рекурсивных шага или, точнее, два шага, которые требовали дальнейших усилий по балансировке. Первый – когда братский узел был красным, и его нужно было сделать черным. Второй – когда родительский, братский и узлы-племянники были черными. Существовали еще три случая: родительский узел был красным, а братский узел и узлы-племянники были черными;

братский узел был черным, а дальний узел-племянник красным (цвет родительского узла и ближайшего узла-племянника "не имели значения");

и, наконец, случай, когда братский узел был черным, дальний узел-племянник черным, а ближайший узел-племянник красным. Если вы еще раз взглянете на рисунки 8.12, 8.13, 8.14 и 8.15, то убедитесь, что мы рассмотрели все варианты.

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

Операция удаления узла из красно-черного дерева реализуется с помощью кода, представленного в листинге 8.25.

Листинг 8.25. Удаление из красно-черного дерева

procedure TtdRedBlackTree.Delete(aItem : pointer);

var

Node : PtdBinTreeNode;

Dad : PtdBinTreeNode;

Child : PtdBinTreeNode;

Brother : PtdBinTreeNode;

FarNephew : PtdBinTreeNode;

NearNephew : PtdBinTreeNode;

IsBalanced : boolean;

ChildType : TtdChildType;

begin

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

Node := bstFindNodeToDelete(aItem);

{если узел красный или является корневым, его можно безнаказанно удалить}

if (Node^.btColor = rbRed) or (Node = FBinTree.Root) then begin

FBinTree.Delete(Node);

dec(FCount);

Exit;

end;

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

if (Node^.btChild[ctLeft] =nil) then

Child := Node^.btChild[ctRight] else

Child :=Node^.btChild[ctLeft];

if IsRed(Child) then begin

Child^.btColor :=rbBlack;

FBinTree.Delete(Node);

dec(FCount);

Exit;

end;

{на этом этапе узел, который нужно удалить, – узел Node; он является черным и известно, что дочерний узел Child, который его заменит, является черным (а также может быть нулевым!) и что существует родительский узел узла Node (который вскоре станет родительским узлом узла Child); братский узел узла Node также существует в соответствии с правилом, сформулированным для черных узлов}

{если узел Child является нулевым, необходимо несколько упростить выполнение цикла и определить родительский и братский узлы и определить, является ли узел Node левым дочерним узлом}

if (Child = nil) then begin

Dad := Node^.btParent;

if (Node = Dad^.btChild[ctLeft]) then begin

ChildType :=ctLeft;

Brother := Dad^.btChild[ctRight];

end

else begin

ChildType :=ctRight;

Brother := Dad^.btChild[ctLeft];

end;

end

else begin

{следующие три строки предназначены просто для введения в заблуждение компилятора и предотвращения вывода ряда ложных предупреждений}

Dad := nil;

Brother := nil;

ChildType :=ctLeft;

end;

{удалить узел – он больше не нужен}

FBinTree.Delete(Node);

dec(FCount);

Node := Child;

{циклически применять алгоритмы балансировки при удалении из красно-черного дерева до тех пор, пока дерево не окажется сбалансированным}

repeat

{предположим, что дерево сбалансировано}

IsBalanced := true;

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

if (Node <> FBinTree.Root) then begin

{получить родительский и братский узлы}

if (Node <> nil) then begin

Dad := Node^.btParent;

if (Node = Dad^.btChild[ctLeft]) then begin

ChildType := ctLeft;

Brother := Dad^.btChild[ctRight];

end

else begin

ChildType := ctRight;

Brother := Dad^.btChild[ctLeft];

end;

end;

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

if (Brother^.btColor = rbRed) then begin

Dad^.btColor := rbRed;

Brother^.btColor :=rbBlack;

rbtPromote(Brother);

IsBalanced := false;

end

{ в противном случае братский узел является черным}

else begin

{получить узлы-племянники, помеченные как дальний и ближний}

if (ChildType = ctLeft) then begin

FarNephew := Brother^.btChild[ctRight];

NearNephew := Brother^.btChild[ctLeft];

end

else begin

FarNephew := Brother^.btChild[ctLeft];

NearNephew := Brother^.btChild[ctRight];

end;

{если дальний узел-племянник является красным (обратите внимание, что он может быть нулевым), окрасить его в черный цвет, братский узел в цвет родительского узла, а родительский узел в красный цвет, а затем повысить ранг братского узла; задача выполнена}

if IsRed( FarNephew) then begin

FarNephew^.btColor :=rbBlack;

Brother^.btColor := Dad^.btColor;

Dad^.btColor :=rbBlack;

rbtPromote(Brother);

end

{в противном случае дальний узел-племянник является черным}

else begin

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

if isRed(NearNephew) then begin

NearNephew^.btColor := Dad^.btColor;

Dad^.btColor :=rbBlack;

rbtPromote(rbtPromote(NearNephew));

end

{в противном случае ближний узел-племянник является также черным}

else begin

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

if (Dad^.btColor = rbRed) then begin

Dad^.btColor :=rbBlack;

Brother^.btColor := rbRed;

end

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

else begin

Brother^.btColor := rbRed;

Node := Dad;

IsBalanced := false;

end;

end;

end;

end;

end;

until IsBalanced;

end;

За исключением перекрытых методов Insert и Delete, класс TtdRedBlackTree не представляет особого интереса. Код интерфейса и дополнительного внутреннего метода, выполняющего повышение ранга узла, приведен в листинге 8.26.

Листинг 8.26. Класс TtdRedBlack и метод повышения ранга узла

type

TtdRedBlackTree = class(TtdBinarySearchTree) private protected

function rbtPromote(aNode : PtdBinTreeNode): PtdBinTreeNode;

public

procedure Delete(aItem : pointer); override;

procedure Insert(aItem : pointer); override;

end;

function TtdRedBlackTree.rbtPromote(aNode : PtdBinTreeNode): PtdBinTreeNode;

var

Parent : PtdBinTreeNode;

begin

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

Parent := aNode^.btParent;

{в обоих случаях существует 6 связей, которые необходимо разорвать и перестроить: связь узла с его дочерним узлом и противоположная связь; связь узла с его родительским узлом и противоположная связь; и связь родительского узла с его родительским узлом и противоположная связь; обратите внимание, что дочерний узел данного узла может быть нулевым}

{повысить ранг левого дочернего узла, т.е. выполнить поворот родительского узла вправо}

if (Parent^.btChild[ctLeft] = aNode) then begin

Parent^.btChild[ctLeft] := aNode^.btChild[ctRight];

if (Parent^.btChild[ctLeft]<> nil) then

Parent^.btChild[ctLeft]^.btParent := Parent;

aNode^.btParent := Parent^.btParent;

if (aNode^.btParent^.btChild[ctLeft] = Parent) then

aNode^.btParent^.btChild[ctLeft] := anode

else

aNode^.btParent^.btChild[ctRight J := aNode;

aNode^.btChild[ctRight] := Parent;

Parent^.btParent := aNode;

end

{повысить ранг правого дочернего узла, т.е. выполнить поворот родительского узла влево}

else begin

Parent^.btChild[ctRight] := aNode^.btChild[ctLeft];

if (Parent^.btChild[ctRight]<> nil) then

Parent^.btChild[ctRight]^.btParent := Parent;

aNode^.btParent := Parent^.btParent;

if (aNode^.btParent^.btChild[ctLeft] = Parent) then

aNode^.btParent^.btChild[ctLeft] := anode else

aNode^.btParent^.btChild[ctRight] := aNode;

aNode^.btChild[ctLeft] := Parent;

Parent^.btParent := aNode;

end;

{вернуть узел, ранг которого был повышен}

Result := aNode;

end;

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

Резюме

В этой главе мы рассмотрели бинарные деревья – важную структуру данных, которая может использоваться во многих прикладных приложениях. Мы рассмотрели стандартное бинарное дерево, а затем перешли к исследованию его сортированной разновидности – дереву бинарного поиска.

В ходе рассмотрения дерева бинарного поиска мы ознакомились с проблемой, которая может возникнуть во время вставки и удаления – проблемой вырождения дерева, – именно в это связи мы исследовали способы ее устранения. Первое решение, скошенное дерево, предоставляет хорошую возможность, несмотря на то, что при этом эффективность вставки и удаления лишь в среднем, а не всегда, описывается соотношением O(log(n)). Однако эта разновидность дерева представляет собой приемлемый компромисс между стандартным деревом бинарного поиска и таким действительно сбалансированным деревом, как красно-черное дерево.

Воспользовавшись красно-черным деревом, мы, наконец, получили полное дерево бинарного поиска, имеющее встроенные алгоритмы балансировки как для вставки, так и для удаления.

Глава 9. Очереди по приоритету и пирамидальная сортировка.

В главе 3 мы рассмотрели несколько очень простых структур данных. Одной из них была очередь. В эту структуру можно было добавлять элементы, а затем извлекать их в порядке поступления. При этом сохранение даты и времени создания записи позволяло не обращать внимания на реальную длину элемента в очереди. Вместо этого мы просто организовали элементы по порядку их поступления в связный список или массив, а затем удаляли их в порядке поступления. При этом использовались две базовые операции: «добавление элемента в очередь» (называемая еще постановкой в очередь) и «удаление самого старого элемента очереди» (или вывод из очереди).

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

Очередь по приоритету

Фактически, упомянутый пример обусловливает название новой структуры данных, называемой очередью по приоритету. Для очереди по приоритету (priority queue) определены две базовых операции: добавление элемента (как и ранее) и извлечение элемента с наивысшим приоритетом. (Естественно, при этом предполагается, что с каждым элементом связано значение приоритета, которое легко проверить.) у читателей может возникнуть вопрос, что в данном контексте понимается под «приоритетом»? Что ж, приоритетом может быть все что угодно. В классическом понимании это численное значение, указывающее на приоритет элемента в каком-либо процессе. Примерами могут служить очереди на печать в операционных системах, очереди заданий или потоки в многопоточной среде. Если принять в качестве примера очередь печати, каждому заданию печати присваивается приоритет – значение, указывающее важность данного задания печати. Задания на печать с высоким приоритетом должны обрабатываться раньше заданий с низким приоритетом. В этом случае операционная система должна была бы завершить выполнение конкретного задания печати, обратиться к очереди печати и извлечь задание печати с наивысшим приоритетом. По мере выполнения работы в операционной системе, другие задания печати будут добавляться в очередь печати с различными приоритетами, а очередь печати обеспечит такую их организацию, чтобы при необходимости можно было определить печатное задание с наивысшим приоритетом.

Однако следует отметить, что используемое в качестве "приоритета" значение не обязательно должно быть классическим номером приоритета. Оно может иметь любой тип или значение – главное, чтобы значения были связаны отношением упорядочения, и чтобы очередь могла определить элемент с наибольшим значением. {Отношение упорядочения набора объектов – это правило, которое позволяет упорядочить объекты так, чтобы объект X был "меньше" объекта Y. Если X меньше Y, то Y не может быть меньше х. Кроме того, если X меньше Y, и Y меньше Z, то X меньше Z. Обычное упорядочение целых чисел, когда 2 меньше 3 и т.д., представляет собой пример отношения упорядочения.}

Например, значением приоритета могло бы быть имя (иначе говоря, строка), а упорядочением мог бы быть стандартный алфавитный порядок. Таким образом, вместо операции извлечения элемента с наибольшим приоритетом можно было бы использовать извлечение элемента, располагающегося раньше в алфавитном порядке (т.е. все А располагаются перед всеми В и т.д.).

Итак, очередь по приоритету должна обеспечивать (1) хранение произвольного количества элементов, (2) добавление в очередь элемента с определенным приоритетом и (3) выявление и удаление элемента с наивысшим приоритетом.

Первая простая реализация

При разработке очереди по приоритету первый атрибут (возможность хранения произвольного количества элементов) наталкивает на мысль об использовании какой-либо расширяемой структуры данных типа связного списка или расширяемого массива, такого как TList. Мы будем использовать (по крайней мере, пока) TList.

Следующий атрибут (возможность добавления элемента в очередь) легко реализовать в случае применения TList: достаточно вызвать метод Add структуры TList. Мы будем исходить из предположения, что добавляемыми в очередь по приоритету элементами будут каким-то образом описанные объекты, свойством которых является их приоритет. В результате мы получаем Достаточно простой элемент, не отвлекающий наше внимание от функциональных возможностей очереди по приоритету.

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

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

Листинг 9.1. Простая очередь по приоритету, построенная на основе структуры TList type

TtdSimplePriQueuel = class private

FCompare : TtdCompareFunc;

FList : TList;

protected

function pqGetCount : integer;

public

constructor Create(aCompare : TtdCompareFunc);

destructor Destroy; override;

function Dequeue : pointer;

procedure Enqueue(aItem : pointer);

property Count : integer read pqGetCount;

end;

constructor TtdSimplePriQueuel.Create(aCompare : TdCompareFunc);

begin

inherited Create;

FCompare := aCompare;

FList := TList.Create;

end;

destructor TtdSimplePriQueuel.Destroy;

begin

FList.Free;

inherited Destroy;

end;

function TtdSimplePriQueuel.Dequeue : pointer;

var

Inx : integer;

PQCount : integer;

MaxInx : integer;

MaxItem : pointer;

begin

PQCount := Count;

if (PQCount = 0) then

Result := nil else

if (PQCount = 1) then begin

Result := FList.List^[0];

FList.Clear;

end

else begin

MaxItem := FList.List^ [0];

MaxInx := 0;

for Inx := 1 to pred(PQCount) do

if (FCompare (FList.List^ [Inx], MaxItem) > 0) then begin

MaxItem := FList.List^[Inx];

MaxInx := Inx;

end;

Result := MaxItem;

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

FList.Count := FList.Count – 1;

end;

end;

procedure TtdSimplePriQueuel.Enqueue(aItem : pointer);

begin

FList.Add(aItem);

end;

function TtdSimplePriQueuel.pqGetCount : integer;

begin

Result := FList.Count;

end;

Из листинга 9.1 видно, что в действительности этот класс является достаточно простым, и даже добавление в него отсутствовавшей ранее проверки на наличие ошибок не делает его громоздким. Единственный фрагмент кода, который представляет интерес – код удаления элемента: мы не вызываем метод Delete структуры данных TList (операция типа O(n)) а просто заменяем элемент, который нужно удалить, последним элементом и уменьшаем на единицу значение счетчика элементов (операция типа O(1)).

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

После того, как мы убедились в простоте разработки создания этой очереди по приоритету, рассмотрим ее эффективность. Во-первых, добавление элемента в очередь по приоритету будет требовать постоянного времени. Иначе говоря, эта операция является операцией типа O(1). Независимо от того, содержит ли очередь ноль или тысячи элементов, добавление нового элемента будет занимать приблизительно одно и то же время: мы всего лишь дописываем его в конец списка.

Теперь рассмотрим противоположную операцию: удаление элемента. В этом случае для отыскания элемента с наивысшим приоритетом потребуется выполнить считывание всех элементов в структуре TList. Этот поиск является последовательным и, как было показано в главе 4, эта операция является операцией типа O(n). Требуемое для этого время пропорционально количеству элементов в очереди.

Таким образом, мы разработали и создали структуру данных, реализующую очередь по приоритету, в которой добавление элемента является операцией типа O(1), а удаление – операцией типа O(n). При наличии небольшого количества элементов эта структура оказывается вполне приемлемой и достаточно эффективной.

Вторая простая реализация

Однако при наличии большого количества элементов или при добавлении и удалении из очереди большого количества элементов она оказывается не столь эффективной, как хотелось бы. Уверен, что читатели сразу подумали об одном возможном способе повышения эффективности: поддержании структуры TList в порядке приоритетов. Иначе говоря, о поддержании ее в отсортированном виде в ходе всех добавлений. По существу, это усовершенствование означает перенос реальной задачи поддержания очереди из операции удаления элемента в операцию вставки элемента. При добавлении элемента необходимо найти для него правильную позицию внутри структуры TList после всех элементов с более низким приоритетом и перед всеми элементами с более высоким приоритетом. В случае выполнения этой дополнительной задачи на этапе добавления все элементы структуры TList будут размещены в порядке своих приоритетов и, следовательно, при удалении элемента потребуется всего лишь удалить последний элемент структуры. Фактически, при этом удаление превращается в операцию типа O(1) (нам точно известно, где расположен элемент с наивысшим приоритетом – он находится в конце очереди, поэтому удаление не зависит от количества элементов).

Вычисление времени, которое требуется для вставки в этот отсортированный список TList, несколько сложнее. Этот процесс проще всего представить сортировкой простыми вставками (которая была описана в главе 5). Мы увеличиваем размер TList на один элемент, а затем, подобно четкам, по одному перемещаем элементы на свободное место, начиная с конца структуры TList. Процесс прекращается по достижении элемента, приоритет которого ниже приоритета элемента, который мы пытаемся вставить. В результате в структуре TList образуется "пробел", в который можно поместить новый элемент. В структуре TList, содержащей n элементов, в среднем придется переместить nil элементов. Следовательно, вставка является операцией типа O(n) (т.е. требуемое для ее выполнения время снова пропорционально количеству элементов в очереди), хотя это усовершенствование позволяет несколько уменьшить время выполнения операции по сравнению с предыдущей реализацией. Пример кода выполнения этих двух операций в описанной структуре данных приведен в листинге 9.2.

Листинг 9.2. Очередь по приоритету, в которой используется отсортированная структура данных TList