типов.
Листинг 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 в порядке приоритетов. Иначе говоря, о поддержании ее в отсортированном виде в ходе всех добавлений. По существу, это усовершенствование означает перенос реальной задачи поддержания очереди из операции удаления элемента в операцию вставки элемента. При добавлении элемента
