Double-Ended Priority Queues:Generic Methods for DEPQs.

Generic Methods for DEPQs

Dual Priority Queues

General methods [8] exist to arrive at efficient DEPQ data structures from single-ended priority queue data structures that also provide an efficient implementation of the remove (the N ode) operation (this operation removes the node the N ode from the PQ). The simplest of these methods, dual structure method, maintains both a min PQ (called min P Q) and a max PQ (called maxP Q) of all the DEPQ elements together with correspondence pointers between the nodes of the min PQ and the max PQ that contain the same element. Figure 8.26 shows a dual heap structure for the elements 6, 7, 2, 5, 4. Correspondence pointers are shown as double-headed arrows.

Although Figure 8.26 shows each element stored in both the min and the max heap, it is necessary to store each element in only one of the two heaps.

The minimum element is at the root of the min heap and the maximum element is at the root of the max heap. To insert an element x, we insert x into both the min and the max heaps and then set up correspondence pointers between the locations of x in the min and max heaps. To remove the minimum element, we do a remove M in from the min heap and a remove(the N ode), where the N ode is the corresponding node for the removed element, from the max heap. The maximum element is removed in an analogous way.

Total Correspondence

The notion of total correspondence borrows heavily from the ideas used in a twin heap [21]. In the twin heap data structure n elements are stored in a min heap using an array min Heap[1 : n] and n other elements are stored in a max heap using the array max Heap[1 :

n]. The min and max heaps satisfy the inequality min Heap[i] ≤ max Heap[i], 1 ≤ i ≤ n.

In this way, we can represent a DEPQ with 2n elements. When we must represent a DEPQ with an odd number of elements, one element is stored in a buffer, and the remaining elements are divided equally between the arrays min Heap and max Heap.

In total correspondence, we remove the positional requirement in the relationship between pairs of elements in the min heap and max heap. The requirement becomes: for each element a in minP Q there is a distinct element b in maxP Q such that a ≤ b and vice versa. (a, b) is a corresponding pair of elements. Figure 8.27(a) shows a twin heap with 11

elements and Figure 8.27(b) shows a total correspondence heap. The broken arrows connect corresponding pairs of elements.

In a twin heap the corresponding pairs (minHeap[i], maxHeap[i]) are implicit, whereas in a total correspondence heap these pairs are represented using explicit pointers.

In a total correspondence DEPQ, the number of nodes is either n or n − 1. The space requirement is half that needed by the dual priority queue representation. The time required is also reduced. For example, if we do a sequence of inserts, every other one simply puts the element in the buffer. The remaining inserts put one element in max P Q and one in min P Q. So, on average, an insert takes time comparable to an insert in either max P Q or min P Q. Recall that when dual priority queues are used the insert time is the sum of the times to insert into max P Q and min P Q. Note also that the size of max P Q and min P Q together is half that of a dual priority queue.

If we assume that the complexity of the insert operation for priority queues as well as 2 remove(the N ode) operations is no more than that of the delete max or min operation (this is true for all known priority queue structures other than weight biased leftist trees [6]), then the complexity of remove M ax and remove M in for total correspondence DEPQs is the same as for the remove M ax and remove M in operation of the underlying priority queue data structure.

Using the notion of total correspondence, we trivially obtain efficient DEPQ structures starting with any of the known priority queue structures (other than weight biased leftist trees [6]).

The remove M ax and remove M in operations can generally be programmed to run faster than suggested by our generic algorithms. This is because, for example, a remove M ax() and put(x) into a max priority queue can often be done faster as a single operation change M ax(x). Similarly a remove(the N ode) and put(x) can be programmed as a change (the N ode, x) operation.

Leaf Correspondence

In leaf correspondence DEPQs, for every leaf element a in min P Q, there is a distinct element b in max P Q such that a ≤ b and for every leaf element c in max P Q there is a distinct element d in min P Q such that d ≤ c.

heap.

Figure 8.28 shows a leaf correspondence Efficient leaf correspondence DEPQs may be constructed easily from PQs that satisfy the following requirements [8]:

(a) The PQ supports the operation remove(Q, p) efficiently.

(b) When an element is inserted into the PQ, no nonleaf node becomes a leaf node (except possibly the node for the newly inserted item).

(c) When an element is deleted (using remove, remove M ax or remove M in) from the PQ, no nonleaf node (except possibly the parent of the deleted node) becomes a leaf node.

Some of the PQ structures that satisfy these requirements are height-biased leftist trees (Chapter 5) [9, 15, 20], pairing heaps (Chapter 7) [12, 19], and Fibonacci heaps [13] (Chapter 7). Requirements (b) and (c) are not satisfied, for example, by ordinary heaps and the FMPQ structure of [3]. Although heaps and Brodal’s FMPQ structure do not satisfy the requirements of our generic approach to build a leaf correspondence DEPQ structure from a priority queue, we can nonetheless arrive at leaf correspondence heaps and leaf correspondence FMPQs using a customized approach.