Double-Ended Priority Queues:Symmetric Min-Max Heaps.

Symmetric Min-Max Heaps

Several simple and efficient implicit data structures have been proposed for the representation of a DEPQ [1, 2, 4, 5, 16, 17, 21]. All of these data structures are adaptations of the classical heap data structure (Chapter 2) for a PQ. Further, in all of these DEPQ data structures, getM ax and getM in take O(1) time and the remaining operations take O(log n) time each (n is the number of elements in the DEPQ). The symmetric min-max heap structure of Arvind and Pandu Rangan [1] is the simplest of the implicit data structures for DEPQs. Therefore, we describe this data structure first.

A symmetric min-max heap (SMMH) is a complete binary tree in which each node other than the root has exactly one element. The root of an SMMH is empty and the total number of nodes in the SMMH is n + 1, where n is the number of elements. Let x be any node of the SMMH. Let elements(x) be the elements in the subtree rooted at x but excluding the element (if any) in x. Assume that elements(x) j= ∅. x satisfies the following properties:

1. The left child of x has the minimum element in elements(x).

2. The right child of x (if any) has the maximum element in elements(x).

Figure 8.1 shows an example SMMH that has 12 elements.

When x denotes the node with 80, elements(x) = {6, 14, 30, 40}; the left child of x has the minimum element 6 in elements(x); and the right child of x has the maximum element 40 in elements(x). You may verify that every node x of this SMMH satisfies the stated properties.

Since an SMMH is a complete binary tree, it is stored as an implicit data structure using the standard mapping of a complete binary tree into an array. When n = 1, the minimum and maximum elements are the same and are in the left child of the root of the SMMH.

When n > 1, the minimum element is in the left child of the root and the maximum is in the right child of the root. So the getM in and getM ax operations take O(1) time.

It is easy to see that an n + 1-node complete binary tree with an empty root and one element in every other node is an SMMH iff the following are true:

P1: For every node x that has a right sibling, the element in x is less than or equal to that in the right sibling of x.

P2: For every node x that has a grandparent, the element in the left child of the grandparent is less than or equal to that in x.

P3: For every node x that has a grandparent, the element in the right child of the grandparent is greater than or equal to that in x.

Notice that if property P1 is satisfied at node x, then at most one of P 2 and P 3 may be violated at x. Using properties P1 through P3 we arrive at simple algorithms to insert and remove elements. These algorithms are simple adaptations of the corresponding algorithms for min and max heaps. Their complexity is O(log n). We describe only the insert operation. Suppose we wish to insert 2 into the SMMH of Figure 8.1. Since an SMMH is a complete binary tree, we must add a new node to the SMMH in the position shown in Figure 8.2; the new node is labeled A. In our example, A will denote an empty node.

If the new element 2 is placed in node A, property P2 is violated as the left child of the grandparent of A has 6. So we move the 6 down to A and obtain Figure 8.3.

Now we see if it is safe to insert the 2 into node A. We first notice that property P1 cannot be violated, because the previous occupant of node A was greater than 2. Similarly, property P3 cannot be violated. Only P2 can be violated only when x = A. So we check P2 with x = A. We see that P2 is violated because the left child of the grandparent of A

has the element 4. So we move the 4 down to A and obtain the configuration shown in Figure 8.4.

For the configuration of Figure 8.4 we see that placing 2 into node A cannot violate property P1, because the previous occupant of node A was greater than 2. Also properties P2 and P3 cannot be violated, because node A has no grandparent. So we insert 2 into node A and obtain Figure 8.5.

Let us now insert 50 into the SMMH of Figure 8.5. Since an SMMH is a complete binary tree, the new node must be positioned as in Figure 8.6.

Since A has a right child of its parent, we first check P1 at node A. If the new element (in this case 50) is smaller than that in the left sibling of A, we swap the new element and the element in the left sibling. In our case, no swap is done. Then we check P2 and P3.

We see that placing 50 into A would violate P3. So the element 40 in the right child of the grandparent of A is moved down to node A.

Figure 8.7 shows the resulting configuration.

Placing 50 into node A of Figure 8.7 cannot create a P1 violation because the previous occupant of node A was smaller. Also, a P2 violation isn’t possible either. So only P3 needs to be checked at A. Since there is no P3 violation at A, 50 is placed into A.

The algorithm to remove either the min or max element is a similar adaptation of the trickle-down algorithm used to remove an element from a min or max heap.