Priority Queues

Our next application of interval arithmetic, global minimization, requires an important data structure: the priority queue. A priority queue supports three operations:

· insert an item into the queue;

· get the largest item currently in the queue; and

· remove the largest item from the queue.

A priority queue is often implemented using a heap. A heap is a binary tree where the item in each node is larger than the items in the left and right subtrees. This condition guarantees that the largest of all items is in the root of the tree. Note that the condition does not require the tree to be completely sorted; therefore, we can hope to find more efficient implementations of the heap operations than are necessary for complete sorting.

A suitable implementation keeps the binary tree in an array such that the root is at position 1 and the left and right subtrees of the node at position i are at positions and , respectively. The number of items currently in the heap is kept in the variable .

To insert an item, first put it at position , then compare it with the item at position and exchange the two if necessary. If an exchange was necessary, set and continue until no exchange is performed or ; the latter condition happens if the new element turns out to be larger than all other items in the heap.

The largest item is always at position 1. To remove it, put the last item at position in its place and then compare it with the larger of the two descendants, exchanging it if necessary until it has found its place. All you ever wanted to know about heaps can, of course, be found in Knuth's The Art of Computer Programming [1].

In our implementation, a new empty queue is created with MakeQueue[]. The optional predicate is used to compare elements; the default is Greater, which will put numbers into descending order. The constructor will store the predicate for later use when inserting items into the queue. An item is inserted into a queue with EnQueue[]. Note that there is no need to reassign the variable you use to store the queue (in the form ), because our implementation uses destructive operations on hidden data. The predicate EmptyQueue[] gives True if is an empty queue. Otherwise, TopQueue[] returns the largest element and DeQueue[] removes it. Again, no assignment to is necessary. On the other hand, if you want to make a copy of the queue, you must use the copy constructor , and if you no longer need a queue you should free its associated storage with DeleteQueue[]. The array used to hold the heap is enlarged as needed. A definition for the format produces a human-readable representation of queues indicating the largest element of the queue.

BeginPackage["PriorityQueue`"]

Begin["`Private`"]

SetAttributes[queue, HoldAll]
SetAttributes[array, HoldAllComplete]

makeArray[n_] := array@@Table[Null, {n}]

MakeQueue[pred_:Greater] :=
  Module[{ar,n=0},
    ar = makeArray[2];
    queue[ar, n, pred]
  ]

CopyQueue[queue[a0_,n0_,pred_]] :=
  Module[{ar=a0,n=n0}, queue[ar, n, pred] ]

EnQueue[q:queue[ar_,n_,pred_], val_] :=
  Module[{i,j},
    If[ n == Length[ar], (* extend (double size) *)
        ar = Join[ar, makeArray[Length[ar]]] ];
    n++;
    ar[[n]] = val; i = n;
    While[ True, (* restore heap *)
      j = Floor[i/2];
      If[ j < 1 || pred[ar[[j]], ar[[i]]], Break[] ];
      {ar[[i]], ar[[j]]} = {ar[[j]], ar[[i]]};
      i = j;
    ];
    q
  ]

EmptyQueue[queue[ar_,n_,pred_]] := n == 0

TopQueue[queue[ar_,n_,pred_]] := ar[[1]]

DeQueue[queue[ar_,n_,pred_]] :=
  Module[{i,j,res=ar[[1]]},
    ar[[1]] = ar[[n]]; ar[[n]] = Null; n--; j = 1;
    While[ j <= Floor[n/2], (* restore heap *)
      i = 2j;
      If[ i < n && pred[ar[[i+1]], ar[[i]]], i++ ];
      If[ pred[ar[[i]], ar[[j]]],
          {ar[[i]], ar[[j]]} = {ar[[j]], ar[[i]]} ];
      j = i
    ];
    res
  ]

DeleteQueue[queue[ar_,n_,pred_]] := (ClearAll[ar,n];)

queue/:Normal[q0_queue] :=
  Module[{l={}, q=CopyQueue[q0]},
    While[!EmptyQueue[q], AppendTo[l, TopQueue[q]]; DeQueue[q]];
    DeleteQueue[q];
    l
  ]

Format[q_queue/;EmptyQueue[q]] := PriorityQueue[]
Format[q_queue] := PriorityQueue[TopQueue[q], "..."]

End[]

EndPackage[]

Listing 3. Priority queues.

For these examples we read in the package containing the queue code.

We create a new queue that sorts its elements into the default decreasing order.

Now, we insert one item, which is, of course, the largest one.

Using Scan, we can insert the elements of a list one by one into the queue.

Here, we look at the largest element without removing it.

For convenience, DeQueue returns the element removed.

For minimization, we will put data of the form , where domain is a list of intervals and res is a single interval, into the queue, sorted by the smallest value in res. Therefore, our predicate will be Min[#1[[2]]]<Min[#2[[2]]]&.

[The Mathematica Programmer Index] [Next Page]