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);
{если данный элемент больше или равен большему дочернему элементу, задача выполнена}
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;