Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
Теперь рассмотрим противоположную операцию: удаление элемента. В этом случае для отыскания элемента с наивысшим приоритетом потребуется выполнить считывание всех элементов в структуре 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
type
TtdSimplePriQueue2 = 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 TtdSimplePriQueue2.Create(aCompare : TtdCompareFunc);
begin
inherited Create;
FCompare := aCompare;
FList := TList.Create;
end;
destructor TtdSimplePriQueue2.Destroy;
begin
FList.Free;
inherited Destroy;
end;
function TtdSimplePriQueue2.Dequeue : pointer;
begin
Result := FList.Last;
FList.Count := FList.Count - 1;
end;
procedure TtdSimplePriQueue2.Enqueue(aItem : pointer);
var
Inx : integer;
begin
{увеличить количество элементов в списке}
FList.Count := FList.Count + 1;
{определить место помещения нового элемента}
Inx := FList.Count -2;
while (Inx>= 0) and (FCompare(FList.List^ [Inx], aItem) > 0) do
begin
FList.List^[Inx+ 1] := FList.List^[Inx];
dec(Inx);
end;
{поместить элемент в эту позицию}
FList.List^[Inx+1] := aItem
end;
function TtdSimplePriQueue2.pqGetCount : integer;
begin
Result := FList.Count;
end;
Исходный код класса TtdSimplePriQueue2 можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDPriQue.pas.
В ходе разработки и создания этой усовершенствованной очереди по приоритету мы перешли от быстрой вставки/медленного удаления к медленной вставке/быстрому удалению. Нельзя ли воспользоваться более эффективным алгоритмом?
Еще одна возможность предполагает полный отказ от использования структуры TList и переход к другой структуре данных: дереву двоичного поиска, описанному в главе 8, или списку с пропусками, описанному в главе 6. При использовании обеих этих структур данных и вставка и удаление являются операциями типа O(log(n)). Иначе говоря, время, требуемое как для вставки, так и для удаления элемента, пропорционально логарифму числа элементов в структуре. Однако применение обеих этих структур данных сопряжено с некоторыми сложностями. В отношении списка с пропусками это связано с его вероятностной структурой, а в отношении дерева двоичного поиска - потому, что в ходе вставки и удаления необходимо заботиться о балансировке результирующего дерева. Существует ли какая-то более простая структура данных?
Сортирующее дерево
Классическая структура данных, используемая для создания очереди по приоритету, известна под названием сортирующего дерева (или "кучи"). Сортирующее дерево (heap), на которое еще ссылаются как на частично упорядоченное полное двоичное дерево, - это двоичное дерево с определенными специальными свойствами и несколькими специальными операциями. (Не путайте эту "кучу" с "кучей", используемой в среде Delphi, -областью памяти, в которой выполняется все распределение памяти.)
Рисунок 9.1. Сортирующее дерево
В дереве двоичного поиска узлы организованы так, что каждый узел больше своего левого дочернего узла и меньше своего правого дочернего узла. Такое упорядочение называется строгим. В сортирующем дереве используется менее строгое упорядочение, называемое пирамидальным свойством. Пирамидальное свойство означает всего лишь, что любой узел в дереве должен быть больше обоих его дочерних узлов. Обратите внимание, что пирамидальное свойство ничего не говорит о порядке дочерних узлов данного узла. Например, оно не утверждает, что левый дочерний узел должен быть меньше правого дочернего узла.
Сортирующее дерево обладает еще одним атрибутом: двоичное дерево должно быть полным. Двоичное дерево называется полным, когда все его уровни, за исключением, быть может, последнего, заполнены. В последнем уровне все узлы размещаются максимально сдвинутыми влево. Полное дерево является максимально сбалансированным. Полное двоичное дерево показано на рис. 9.1.
Так как же эта структура может помочь в наших поисках идеальной структуры очереди по приоритету? Что ж, операции вставки и удаления при использовании сортирующего дерева являются операциями типа O(log(n)), но они выполняются значительно быстрее, чем эти же операции в дереве двоичного поиска, независимо от того, является ли оно сбалансированным. Это тот случай, когда О-нотация оказывается неприемлемой - она не позволяет количественно определить, какая из двух операций с одним и тем же значением О большого действительно выполняется быстрее.
Вставка в сортирующее дерево
Рассмотрим алгоритмы вставки и удаления. Вначале ознакомимся со вставкой. Чтобы вставить элемент в сортирующее дерево, мы добавляем его в конец этого дерева, в единственную позицию, которая соответствует требованию полноты (на рис. 5 этой позицией была бы позиция правого дочернего узла пятого узла).
Этот атрибут сортирующего дерева сохраняется. При этом может быть нарушен второй атрибут - пирамидальность. Новый узел может быть большего своего родительского узла, поэтому потребуется исправить дерево и восстановить свойство пирамидальности.
Если этот новый дочерний узел больше своего родительского узла, мы меняем его местами с родительским узлом. В своей новой позиции новый узел может быть все же больше своего нового родительского узла, и поэтому их нужно снова поменять местами. Мы продолжаем такое перемещение по сортирующему дереву до тех пор, пока не будет достигнута точка, в которой новый узел не больше родительского узла или пока не достигнем корневого узла дерева. Выполнение упомянутого алгоритма обеспечивает, чтобы все узлы были больше обоих своих дочерних узлов, и, таким образом, свойство пирамидальности восстанавливается. Этот алгоритм называется алгоритмом пузырькового подъема (bubble up), поскольку новый узел подобно пузырьку воздуха "всплывает" вверх, пока не попадает в требуемую позицию (либо в позиции корневого узла, либо под узлом, который больше него).
По существу, свойство пирамидальности гарантирует размещение наибольшего элемента в позиции корневого узла. Это достаточно легко доказать: если бы наибольший элемент размещался не в позиции корневого узла, он имел бы родительский узел. Поскольку он является наибольшим элементом, мы были бы вынуждены заключить, что он больше своего родительского узла, - а это является нарушением свойства пирамидальности. Следовательно, первоначальное предположение, что наибольший узел размещается не в позиции корневого узла, неверно.
