Double-Ended Priority Queues:Interval Heaps.

Interval Heaps

The twin heaps of [21], the min-max pair heaps of [17], the interval heaps of [11, 16], and the diamond deques of [5] are virtually identical data structures. In each of these structures, an n element DEPQ is represented by a min heap with In/2l elements and a max heap with the remaining ln/2J elements. The two heaps satisfy the property that each element in the min heap is ≤ the corresponding element (two elements correspond if they occupy the same position in their respective binary trees) in the max heap. When the number of elements in the DEPQ is odd, the min heap has one element (i.e., element In/2l) that has no corresponding element in the max heap. In the twin heaps of [21], this is handled as a special case and one element is kept outside of the two heaps. In min-max pair heaps, interval heaps, and diamond deques, the case when n is odd is handled by requiring element In/2l of the min heap to be ≤ element ln/4J of the max heap.

In the twin heaps of [21], the min and max heaps are stored in two arrays min and max

using the standard array representation of a complete binary tree2 [15]. The correspondence property becomes min[i] ≤ max[i], 1 ≤ i ≤ ln/2J. In the min-max pair heaps of [17] and the interval heaps of [16], the two heaps are stored in a single array minmax and we have minmax[i].min being the i’th element of the min heap, 1 ≤ i ≤ In/2l and minmax[i].max being the i’th element of the max heap, 1 ≤ i ≤ ln/2J. In the diamond deque [5], the two heaps are mapped into a single array with the min heap occupying even positions (beginning with position 0) and the max heap occupying odd positions (beginning with position 1). Since this mapping is slightly more complex than the ones used in twin heaps, min-max pair heaps, and interval heaps, actual implementations of the diamond deque are expected to be slightly slower than implementations of the remaining three structures.

Since the twin heaps of [21], the min-max pair heaps of [17], the interval heaps of [16], and the diamond deques of [5] are virtually identical data structures, we describe only one of these—interval heaps—in detail. An interval heap is a complete binary tree in which each node, except possibly the last one (the nodes of the complete binary tree are ordered using a level order traversal), contains two elements. Let the two elements in node P be a and b, where a ≤ b. We say that the node P represents the closed interval [a, b]. a is the left end point of the interval of P , and b is its right end point.

The interval [c, d] is contained in the interval [a, b] iff a ≤ c ≤ d ≤ b. In an interval heap, the intervals represented by the left and right children (if they exist) of each node P are contained in the interval represented by P . When the last node contains a single element c, then a ≤ c ≤ b, where [a, b] is the interval of the parent (if any) of the last node.

Figure 8.8 shows an interval heap with 26 elements. You may verify that the intervals represented by the children of any node P are contained in the interval of P .

The following facts are immediate:

1. The left end points of the node intervals define a min heap, and the right end points define a max heap. In case the number of elements is odd, the last node has a single element which may be regarded as a member of either the min or max heap. Figure 8.9 shows the min and max heaps defined by the interval heap of Figure 8.8.

2. When the root has two elements, the left end point of the root is the minimum element in the interval heap and the right end point is the maximum. When

the root has only one element, the interval heap contains just one element. This element is both the minimum and maximum element.

3. An interval heap can be represented compactly by mapping into an array as is done for ordinary heaps. However, now, each array position must have space for two elements.

4. The height of an interval heap with n elements is Θ(log n).

Inserting an Element

Suppose we are to insert an element into the interval heap of Figure 8.8. Since this heap currently has an even number of elements, the heap following the insertion will have an additional node A as is shown in Figure 8.10.

The interval for the parent of the new node A is [6, 15]. Therefore, if the new element is between 6 and 15, the new element may be inserted into node A. When the new element is less than the left end point 6 of the parent interval, the new element is inserted into the min heap embedded in the interval heap. This insertion is done using the min heap insertion procedure starting at node A. When the new element is greater than the right end point 15 of the parent interval, the new element is inserted into the max heap embedded in the interval heap. This insertion is done using the max heap insertion procedure starting at node A.

If we are to insert the element 10 into the interval heap of Figure 8.8, this element is put into the node A shown in Figure 8.10. To insert the element 3, we follow a path from node A towards the root, moving left end points down until we either pass the root or reach a node whose left end point is ≤ 3. The new element is inserted into the node that now has

no left end point. Figure 8.11 shows the resulting interval heap.

To insert the element 40 into the interval heap of Figure 8.8, we follow a path from node A (see Figure 8.10) towards the root, moving right end points down until we either pass the root or reach a node whose right end point is ≥ 40. The new element is inserted into the node that now has no right end point. Figure 8.12 shows the resulting interval heap.

Now, suppose we wish to insert an element into the interval heap of Figure 8.12. Since this interval heap has an odd number of elements, the insertion of the new element does not increase the number of nodes. The insertion procedure is the same as for the case when we initially have an even number of elements. Let A denote the last node in the heap. If the new element lies within the interval [6, 15] of the parent of A, then the new element is inserted into node A (the new element becomes the left end point of A if it is less than the element currently in A). If the new element is less than the left end point 6 of the parent of A, then the new element is inserted into the embedded min heap; otherwise, the new element is inserted into the embedded max heap. Figure 8.13 shows the result of inserting the element 32 into the interval heap of Figure 8.12.

Removing the Min Element

The removal of the minimum element is handled as several cases:

1. When the interval heap is empty, the removeM in operation fails.

2. When the interval heap has only one element, this element is the element to be returned. We leave behind an empty interval heap.

3. When there is more than one element, the left end point of the root is to be

returned. This point is removed from the root. If the root is the last node of the interval heap, nothing more is to be done. When the last node is not the root node, we remove the left point p from the last node. If this causes the last node to become empty, the last node is no longer part of the heap. The point p removed from the last node is reinserted into the embedded min heap by beginning at the root. As we move down, it may be necessary to swap the current p with the right end point r of the node being examined to ensure that p ≤ r. The reinsertion is done using the same strategy as used to reinsert into an ordinary heap.

Let us remove the minimum element from the interval heap of Figure 8.13. First, the element 2 is removed from the root. Next, the left end point 15 is removed from the last node and we begin the reinsertion procedure at the root. The smaller of the min heap elements that are the children of the root is 3. Since this element is smaller than 15, we move the 3 into the root (the 3 becomes the left end point of the root) and position ourselves at the left child B of the root. Since, 15 ≤ 17 we do not swap the right end point of B with the current p = 15. The smaller of the left end points of the children of B is 3. The 3 is moved from node C into node B as its left end point and we position ourselves at node C.

Since p = 15 > 11, we swap the two and 15 becomes the right end point of node C. The smaller of left end points of Cs children is 4. Since this is smaller than the current p = 11, it is moved into node C as this node’s left end point. We now position ourselves at node D.

First, we swap p = 11 and Ds right end point. Now, since D has no children, the current p = 7 is inserted into node D as Ds left end point. Figure 8.14 shows the result.

The max element may removed using an analogous procedure.

Initializing an Interval Heap

Interval heaps may be initialized using a strategy similar to that used to initialize ordinary heaps–work your way from the heap bottom to the root ensuring that each subtree is an interval heap. For each subtree, first order the elements in the root; then reinsert the left end point of this subtree’s root using the reinsertion strategy used for the removeM in operation, then reinsert the right end point of this subtree’s root using the strategy used for the removeM ax operation.

Complexity of Interval Heap Operations

The operations isEmpty(), size(), getM in(), and getM ax() take O(1) time each; put(x), removeM in(), and removeM ax() take O(log n) each; and initializing an n element interval heap takes O(n) time.

The Complementary Range Search Problem

In the complementary range search problem, we have a dynamic collection (i.e., points are added and removed from the collection as time goes on) of one-dimensional points (i.e., points have only an x-coordinate associated with them) and we are to answer queries of the form: what are the points outside of the interval [a, b]? For example, if the point collection is 3, 4, 5, 6, 8, 12, the points outside the range [5, 7] are 3, 4, 8, 12.

When an interval heap is used to represent the point collection, a new point can be inserted or an old one removed in O(log n) time, where n is the number of points in the collection. Note that given the location of an arbitrary element in an interval heap, this element can be removed from the interval heap in O(log n) time using an algorithm similar to that used to remove an arbitrary element from a heap.

The complementary range query can be answered in Θ(k) time, where k is the number of points outside the range [a, b]. This is done using the following recursive procedure:

1. If the interval tree is empty, return.

2. If the root interval is contained in [a, b], then all points are in the range (therefore, there are no points to report), return.

3. Report the end points of the root interval that are not in the range [a, b].

4. Recursively search the left subtree of the root for additional points that are not in the range [a, b].

5. Recursively search the right subtree of the root for additional points that are not in the range [a, b].

6. return

Let us try this procedure on the interval heap of Figure 8.13. The query interval is [4, 32]. We start at the root. Since the root interval is not contained in the query interval, we reach step 3 of the procedure. Whenever step 3 is reached, we are assured that at least one of the end points of the root interval is outside the query interval. Therefore, each time step 3 is reached, at least one point is reported. In our example, both points 2 and 40 are outside the query interval and so are reported. We then search the left and right subtrees of the root for additional points. When the left subtree is searched, we again determine that the root interval is not contained in the query interval. This time only one of the root interval points (i.e., 3) is to be outside the query range. This point is reported and we proceed to search the left and right subtrees of B for additional points outside the query range. Since the interval of the left child of B is contained in the query range, the left subtree of B contains no points outside the query range. We do not explore the left subtree of B further. When the right subtree of B is searched, we report the left end point 3 of node C and proceed to search the left and right subtrees of C. Since the intervals of the roots of each of these subtrees is contained in the query interval, these subtrees are not explored further. Finally, we examine the root of the right subtree of the overall tree root, that is the node with interval [4, 32]. Since this node’s interval is contained in the query interval, the right subtree of the overall tree is not searched further.

The complexity of the above six step procedure is Θ(number of interval heap nodes visited). The nodes visited in the preceding example are the root and its two children, node B and its two children, and node C and its two children. Thus, 7 nodes are visited and a total of 4 points are reported.

We show that the total number of interval heap nodes visited is at most 3k + 1, where k is the number of points reported. If a visited node reports one or two points, give the node a count of one. If a visited node reports no points, give it a count of zero and add one to the count of its parent (unless the node is the root and so has no parent). The number of nodes with a nonzero count is at most k. Since no node has a count more than 3, the sum of the counts is at most 3k. Accounting for the possibility that the root reports no point, we see that the number of nodes visited is at most 3k + 1. Therefore, the complexity of the search is Θ(k). This complexity is asymptotically optimal because every algorithm that reports k points must spend at least Θ(1) time per reported point.

In our example search, the root gets a count of 2 (1 because it is visited and reports at least one point and another 1 because its right child is visited but reports no point), node B gets a count of 2 (1 because it is visited and reports at least one point and another 1 because its left child is visited but reports no point), and node C gets a count of 3 (1 because it is visited and reports at least one point and another 2 because its left and right children are visited and neither reports a point). The count for each of the remaining nodes in the interval heap is 0.