Double-Ended Priority Queues:Min-Max Heaps.

Min-Max Heaps

In the min-max heap structure [2], all n DEPQ elements are stored in an n-node complete binary tree with alternating levels being min levels and max levels (Figure 8.15, nodes at max levels are shaded). The root level of a min-max heap is a min level. Nodes on a min level are called min nodes while those on a max level are max nodes. Every min (max) node has the property that its value is the smallest (largest) value in the subtree of which it is the root. Since 5 is in a min node of Figure 8.15, it is the smallest value in its subtree. Also, since 30 and 26 are in max nodes, these are the largest values in the subtrees of which they are the root.

The following observations are a direct consequence of the definition of a min-max heap.

1. When n = 0, there is no min nor max element.

2. When n = 1, the element in the root is both the min and the max element.

3. When n > 1, the element in the root is the min element; the max element is one of the up to two children of the root.

From these observations, it follows that get M in() and get M ax() can be done in O(1) time each.

Inserting an Element

When inserting an element new Element into a min-max heap that has n elements, we go from a complete binary tree that has n nodes to one that has n+1 nodes. So, for example, an insertion into the 12-element min-max heap of Figure 8.15 results in the 13-node complete binary tree of Figure 8.16.

When n = 0, the insertion simply creates a min-max heap that has a single node that contains the new element. Assume that n > 0 and let the element in the parent, parent N ode, of the new node j be parent Element. If new Element is placed in the new node j, the min- and max-node property can be violated only for nodes on the path from the root to parent N ode. So, the insertion of an element need only be concerned with ensuring that nodes on this path satisfy the required min- and max-node property. There are three cases to consider.

1. parentElement = newElement

In this case, we may place newElement into node j. With such a placement, the min- and max-node properties of all nodes on the path from the root to parentN ode are satisfied.

2. parentN ode > newElement

If parent N ode is a min node, we get a min-node violation. When a min-node violation occurs, we know that all max nodes on the path from the root to parent N ode are greater than new Element. So, a min-node violation may be fixed by using the trickle-up process used to insert into a min heap; this trickle- up process involves only the min nodes on the path from the root to parent N ode. For example, suppose that we are to insert new Element = 2 into the min-max heap of Figure 8.15. The min nodes on the path from the root to parent N ode have values 5 and 20. The 20 and the 5 move down on the path and the 2 trickles up to the root node. Figure 8.17 shows the result. When new Element = 15, only the 20 moves down and the sequence of min nodes on the path from the root to j have values 5, 15, 20.

The case when parent N ode is a max node is similar.

3. parent N ode < new Element

When parentN ode is a min node, we conclude that all min nodes on the path from the root to parent N ode are smaller than new Element. So, we need be concerned only with the max nodes (if any) on the path from the root to parent N ode. A trickle-up process is used to correctly position new Element with respect to the elements in the max nodes of this path. For the example of Figure 8.16, there is only one max node on the path to parent N ode. This max node has the element 26. If new Element > 26, the 26 moves down to j and new Element trickles up to the former position of 26 (Figure 8.18 shows the case when newElement = 32). If newElement < 26, newElement is placed in j.

The case when parentN ode is a max node is similar.

Since the height of a min-max heap is Θ(log n) and a trickle-up examines a single element at at most every other level of the min-max heap, an insert can be done in O(log n) time.

Removing the Min Element

When n = 0, there is no min element to remove. When n = 1, the min-max heap becomes empty following the removal of the min element, which is in the root. So assume that n > 1. Following the removal of the min element, which is in the root, we need to go from an n-element complete binary tree to an (n − 1)-element complete binary tree. This causes the element in position n of the min-max heap array to drop out of the min-max

heap. Figure 8.17 shows the situation following the removal of the min element, 5, from the min-max heap of Figure 8.15. In addition to the 5, which was the min element and which has been removed from the min-max heap, the 22 that was in position n = 12 of the min-max heap array has dropped out of the min-max heap. To get the dropped-out element 22 back into the min-max heap, we perform a trickle-down operation that begins at the root of the min-max heap.

The trickle-down operation for min-max heaps is similar to that for min and max heaps. The root is to contain the smallest element. To ensure this, we determine the smallest element in a child or grandchild of the root. If 22 is ≤ the smallest of these children and grandchildren, the 22 is placed in the root. If not, the smallest of the children and grandchildren is moved to the root; the trickle-down process is continued from the position vacated by the just moved smallest element.

In our example, examining the children and grandchildren of the root of Figure 8.19, we determine that the smallest of these is 10. Since 10 < 22, the 10 moves to the root and the 22 trickles down (Figure 8.20).

A special case arises when this trickle down of the 22 by 2 levels causes the 22 to trickle past a smaller element (in our example, we trickle past a larger element 30). When this special case arises, we simply exchange the 22 and the smaller element being trickled past. The trickle-down process applied at the vacant node

of Figure 8.20 results in the 22 being placed into the vacant node.

Suppose that droppedElement is the element dropped from minmaxHeap[n] when a remove min is done from an n-element min-max heap. The following describes the trickle- down process used to reinsert the dropped element.

1. The root has no children.

In this case dropped Element is inserted into the root and the trickle down terminates.

2. The root has at least one child.

Now the smallest key in the min-max heap is in one of the children or grandchildren of the root. We determine which of these nodes has the smallest key. Let this be node k. The following possibilities need to be considered:

(a) dropped Element ≤ minmaxHeap[k].

dropped Element may be inserted into the root, as there is no smaller element in the heap. The trickle down terminates.

(b) droppedElement > minmaxHeap[k] and k is a child of the root.

Since k is a max node, it has no descendants larger than minmaxHeap[k].

Hence, node k has no descendants larger than dropped Element. So, the minmaxHeap[k] may be moved to the root, and droppedElement placed into node k. The trickle down terminates.

(c) droppedElement > minmaxHeap[k] and k is a grandchild of the root.

minmaxHeap[k] is moved to the root. Let p be the parent of k. If droppedElement

> minmaxHeap[p], then minmaxHeap[p] and droppedElement are interchanged. This interchange ensures that the max node p contains the largest key in the subheap with root p. The trickle down continues with k as the root of a min-max (sub) heap into which an element is to be inserted.

The complexity of the remove-min operation is readily seen to be O(log n). The remove- max operation is similar to the remove-min operation, and min-max heaps may be initialized in Θ(n) time using an algorithm similar to that used to initialize min and max heaps [15].