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