Implementation of a Priority Queue with a Heap

Listing 9.3 shows the interface for our final priority queue which uses a heap implemented by a TList.

Listing 9.3: TtdPriorityQueue class interface

type

TtdPriorityQueue = class

private

FCompare : TtdCompareFunc;

FDispose : TtdDisposeProc;

FList : TList;

FName : TtdNameString;

protected

function pqGetCount : integer;

procedure pqError(aErrorCode

: integer;

const aMethodName

: TtdNameString);

procedure pqBubbleUp(aFromInx

: integer);

procedure pqTrickleDown;

procedure pqTrickleDownStd;

public

constructor Create(aCompare :

TtdCompareFunc;

aDispose :

TtdDisposeProc);

destructor Destroy; override;

procedure Clear;

function Dequeue : pointer;

procedure Enqueue(aItem : pointer);

function Examine : pointer;

function IsEmpty : boolean;

property Count : integer read pqGetCount;

property Name : TtdNameString read FName write FName;

end;

The Create constructor and Destroy destructor are both fairly simple to implement: the former has to create the internal TList instance, and the latter just needs to free the internal TList. Like a standard queue, Create requires an item disposal routine so that it can free items if need be, but unlike the standard queue, we now need a comparison routine so that we can compare two items to find the larger.

Listing 9.4: The constructor and destructor for the priority queue

constructor TtdPriorityQueue.Create(aCompare :

TtdCompareFunc;

aDispose

: TtdDisposeProc);

begin

inherited Create;

if not Assigned(aCompare) then

pqError(tdePriQueueNoCompare, 'Create'); FCompare := aCompare; FDispose := aDispose; FList := TList.Create; end;

destructor TtdPriorityQueue.Destroy; begin Clear; FList.Free; inherited Destroy; end;

Listing 9.5 shows the insertion algorithm, together with the routine that performs the actual bubble up operation. The insertion operation has been written to ensure that the largest item is found at the root. This type of priority queue is usually known as a max-heap. If we change the sense of the comparison routine so that a negative number is returned if the first item is larger than the second, the priority queue will have the smallest item at the root, and it is known as a min-heap instead.

Listing 9.5: Insertion into a TtdPriorityQueue: Enqueue procedure TtdPriorityQueue.pqBubbleUp(aFromInx : integer); var

ParentInx : integer; Item : pointer;

begin

Item := FList.List~[aFromInx];

  • while the item under consideration is larger than its parent, swap it with its parent and continue from its new position} {Note: the parent for the child at index n is at n-1 div 2} ParentInx := (aFromInx - 1) div 2;
  • while our item has a parent, and it's greater than the parent...} while (aFromInx > 0) and
  • FCompare(Item, FList.List~[ParentInx]) > 0) do begin {move our parent down the tree} FList.List~[aFromInx] := FList.List~[ParentInx]; aFromInx := ParentInx; ParentInx := (aFromInx - 1) div 2; end;
  • store our item in the correct place} FList.List~[aFromInx] := Item; end;

procedure TtdPriorityQueue.Enqueue(aItem : pointer); begin

{add the item to the end of the list and bubble it up as far as it will go}

FList.Add(aItem);

pqBubbleUp(pred(FList.Count)); end;

Listing 9.6 shows the final jigsaw piece for the priority queue: the deletion algorithm together with the routine that performs the trickle down operation.

Listing 9.6: Deletion from a TtdPriorityQueue: Dequeue procedure TtdPriorityQueue.pqTrickleDownStd; var

FromInx : integer; ChildInx : integer; MaxInx : integer; Item : pointer;

begin

MaxInx := FList.Count - 1;

  • while the item under consideration is smaller than one of its children, swap it with the larger child and continue from its new position}
  • Note: the children for the parent at index n are at 2n+1 and 2n+2} ChildInx := (FromInx * 2) + 1; { while there is at least a left child... } while (ChildInx <= MaxInx) do begin
  • if there is a right child as well, calculate the index of the larger child}

if (succ(ChildInx) <= MaxInx) and (FCompare(FList.List~[ChildInx],

FList.List~[succ(ChildInx)]) < 0) then inc(ChildInx);

  • if our item is greater or equal to the larger child, we're done} if (FCompare(Item, FList.List~[ChildInx]) >= 0) then Break;
  • otherwise move the larger child up the tree, and move our item down the tree and repeat}

FList.List~[FromInx] := FList.List~[ChildInx]; FromInx := ChildInx; ChildInx := (FromInx * 2) + 1; end;

{store our item in the correct place} FList.List~[FromInx] := Item; end;

function TtdPriorityQueue.Dequeue : pointer; begin

{make sure we have an item to dequeue} if (FList.Count = 0) then pqError(tdeQueueIsEmpty, 'Dequeue'); {return the item at the root}

Result := FList.List~[0];

  • if there was only one item in the queue, it's now empty} if (FList.Count = 1) then FList.Count := 0
  • if there were two, just replace the root with the one remaining child; the heap property is obviously satisfied} else if (FList.Count = 2) then begin FList.List~[0] := FList.List~[1]; FList.Count := 1; end
  • otherwise we have to restore the heap property}

else begin

{replace the root with the child at the lowest, rightmost position, shrink the list, and finally trickle down the root item as far as it will go} FList.List~[0] := FList.Last; FList.Count := FList.Count - 1; pqTrickleDownStd; end; end;

Notice that at each stage through the loop in the trickle down algorithm, as we move down the heap, we make at most two comparisons: comparing the two children to find the larger and comparing the larger child with the parent to see if we need to exchange them. Compared with the bubble up operation with its single comparison at each level as we move up the heap, it seems a little excessive. Is there anything we can do to alleviate the situation?

Robert Floyd pointed out that the first step of the dequeue operation involves removing the item with the largest priority and replacing it with one of the smallest items in the heap. Not necessarily the smallest, mind you, but it's certainly going to move down to near the bottom level of the tree when we apply the trickle down algorithm. In other words, the majority of the comparisons we make between the parent and its larger child during the trickle down process are probably not worth doing, as the result of the comparison is going to be a foregone conclusion: the parent will be less than its larger child. What Floyd proposed was this: completely ignore the parent-larger child comparisons in the trickle down process and always exchange the parent with its larger child. Eventually, of course, we shall reach the bottom of the heap, and the item may be in the wrong place (in other words, it may be larger than its parent). No matter; we then just apply the bubble up operation. Since the item we were trickling down was one of the smallest items in the heap, it is likely that we won't have to bubble it up very far, if at all.

This optimization cuts the number of comparisons made during a dequeue operation by roughly half. If the comparisons are time-intensive (for example, comparing strings), this optimization is worthwhile. In our implementation of a priority queue, where we use a comparison function rather than a simple comparison between integers, etc., it is also worthwhile to apply this optimization.

Listing 9.7: Optimized trickle down operation procedure TtdPriorityQueue.pqTrickleDown; var

FromInx : integer; ChildInx : integer; MaxInx : integer; Item : pointer;

begin

MaxInx := pred(FList.Count);

  • swap the item under consideration with its larger child until it has no children}
  • Note: the children for the parent at index n are at 2n+1 and 2n+2}

while (ChildInx <= MaxInx) do begin

{if there is a right child as well, calculate the index of the larger child}

if (succ(ChildInx) <= MaxInx) and (FCompare(FList.List~[ChildInx],

  1. List~[succ(ChildInx)]) < 0) then inc(ChildInx); {move the larger child up the tree, and move our item down the tree and repeat}
  2. List~[FromInx] := FList.List~[ChildInx]; FromInx := ChildInx; ChildInx := (FromInx * 2) + 1; end;

{store our item where we end up} FList.List~[FromInx] := Item; {now bubble this item up the tree} pqBubbleUp(FromInx); end;

The source code for the TtdPriorityQueue class can be found in the TDPriQue.pas file on the CD.

Was this article helpful?

+1 0

Post a comment