Priority QueuesOur 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 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
Here, we look at the largest element without removing it.
For convenience,
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 Converted by Mathematica May 8, 2000 |