Double-Ended Priority Queues: Deaps.

Deaps

The deap structure of [4] is similar to the two-heap structures of [5, 16, 17, 21]. At the conceptual level, we have a min heap and a max heap. However, the distribution of elements between the two is not In/2l and ln/2J. Rather, we begin with an (n + 1)-node complete binary tree. Its left subtree is the min heap and its right subtree is the max heap (Figure 8.21, max-heap nodes are shaded). The correspondence property for deaps is slightly more complex than that for the two-heap structures of [5, 16, 17, 21].

A deap is a complete binary tree that is either empty or satisfies the following conditions:

1. The root is empty.

2. The left subtree is a min heap and the right subtree is a max heap.

3. Correspondence property. Suppose that the right subtree is not empty. For every node x in the left subtree, define its corresponding node y in the right subtree to be the node in the same position as x. In case such a y doesn’t exist, let y be the corresponding node for the parent of x. The element in x is ≤ the element in y.

For the example complete binary tree of Figure 8.21, the corresponding nodes for the nodes with 3, 7, 5, 9, 15, 11, and 12, respectively, have 20, 18, 16, 10, 18, 16, and 16.

Notice that every node y in the max heap has a unique corresponding node x in the min heap. The correspondence property for max-heap nodes is that the element in y be ≥ the element in x. When the correspondence property is satisfied for all nodes in the min heap, this property is also satisfied for all nodes in the max heap.

We see that when n = 0, there is no min or max element, when n = 1, the root of the min heap has both the min and the max element, and when n> 1, the root of the min heap is the min element and the root of the max heap is the max element. So, both get M in() and getM ax() may be implemented to work in O(1) time.

Inserting an Element

When an element is inserted into an n-element deap, we go form a complete binary tree that has n + 1 nodes to one that has n + 2 nodes. So, the shape of the new deap is well defined. Following an insertion, our 11-element deap of Figure 8.21 has the shape shown in Figure 8.22. The new node is node j and its corresponding node is node i.

To insert new Element, temporarily place new Element into the new node j and check the correspondence property for node j. If the property isn’t satisfied, swap new Element and the element in its corresponding node; use a trickle-up process to correctly position new Element in the heap for the corresponding node i. If the correspondence property is satisfied, do not swap new Element; instead use a trickle-up process to correctly place new Element in the heap that contains node j.

Consider the insertion of new Element = 2 into Figure 8.22. The element in the corresponding node i is 15. Since the correspondence property isn’t satisfied, we swap 2 and 15. Node j now contains 15 and this swap is guaranteed to preserve the max-heap properties of the right subtree of the complete binary tree. To correctly position the 2 in the left subtree, we use the standard min-heap trickle-up process beginning at node i. This results in the configuration of Figure 8.23.

To insert newElement = 19 into the deap of Figure 8.22, we check the correspondence property between 15 and 19. The property is satisfied. So, we use the trickle-up process for max heaps to correctly position newElement in the max heap. result.

Figure 8.24 shows the Since the height of a deap is Θ(log n), the time to insert into a deap is O(log n).

Removing the Min Element

Assume that n > 0. The min element is in the root of the min heap. Following its removal, the deap size reduces to n − 1 and the element in position n + 1 of the deap array is dropped from the deap. In the case of our example of Figure 8.21, the min element 3 is removed and the 10 is dropped. To reinsert the dropped element, we first trickle the vacancy in the root of the min heap down to a leaf of the min heap. This is similar to a standard min-heap trickle down with ∞ as the reinsert element. For our example, this trickle down causes 5 and 11 to, respectively, move to their parent nodes. Then, the dropped element 10 is inserted using a trickle-up process beginning at the vacant leaf of the min heap. The resulting deap is shown in Figure 8.25.

Since a removeM in requires a trickle-down pass followed by a trickle-up pass and since the height of a deap is Θ(log n), the time for a removeM in is O(log n). A removeM ax is similar. Also, we may initialize a deap in Θ(n) time using an algorithm similar to that used to initialize a min or max heap [15].