Skew Heaps:Meldable Priority Queues and Skew Heaps

Meldable Priority Queues and Skew Heaps

DEFINITION 6.2 [Skew Heaps] A Skew Heap is simply a binary tree. Values are stored in the structure, one per node, satisfying the heap-order property: A value stored at a node is larger than the value stored at its parent, except for the root (as root has no parent).

REMARK 6.2 Throughout our discussion, we handle sets with distinct items. Thus a set of n items is represented by a skew heap of n nodes. The minimum of the set is always at the root. On any path starting from the root and descending towards a leaf, the values are in increasing order.

6.3.1 Meldable Priority Queue Operations

Recall that a Meldable Priority queue supports three key operations: insert, delete-min and meld. We will first describe the meld operation and then indicate how other two operations can be performed in terms of the meld operation.

Let S1 and S2 be two sets and H1 and H2 be Skew Heaps storing S1 and S2 respectively. Recall that S1 ∩ S2 = φ. The meld operation should produce a single Skew Heap storing the values in S1 ∪ S2. The procedure meld (H1, H2) consists of two phases. In the first phase, the two right most paths are merged to obtain a single right most path. This phase is pretty much like the merging algorithm working on sorted sequences. In this phase, the left subtrees of nodes in the right most paths are not disturbed. In the second phase, we simply swap the children of every node on the merged path except for the lowest. This completes the process of melding.

Figures 6.1, 6.2 and 6.3 clarify the phases involved in the meld routine.

Figure 6.1 shows two Skew Heaps H1 and H2. In Figure 6.2 we have shown the scenario after the completion of the first phase. Notice that right most paths are merged to obtain the right most path of a single tree, keeping the respective left subtrees intact. The final

Skew Heap is obtained in Figure 6.3. Note that left and right child of every node on the right most path of the tree in Figure 6.2 (except the lowest) are swapped to obtain the final Skew Heap.

It is easy to implement delete-min and insert in terms of the meld operation. Since minimum is always found at the root, delete-min is done by simply removing the root and melding its left subtree and right subtree. To insert an item x in a Skew Heap H1, we create a Skew Heap H2 consisting of only one node containing x and then meld H1 and H2. From the above discussion, it is clear that cost of meld essentially determines the cost of insert and delete-min. In the next section, we analyze the amortized cost of meld operation.

6.3.2 Amortized Cost of Meld Operation

At this juncture we are left with the crucial task of identifying a suitable potential function. Before proceeding further, perhaps one should try the implication of certain simple potential functions and experiment with the resulting amortized cost. For example, you may try the function f (D) = number of nodes in D( and discover how ineffective it is!).

We need some definitions to arrive at our potential function.

DEFINITION 6.3 For any node x in a binary tree, the weight of x, denoted wt(x), is the number of descendants of x, including itself. A non-root node x is said to be heavy if wt(x) > wt(parent(x))/2. A non-root node that is not heavy is called light. The root is neither light nor heavy.

The next lemma is an easy consequence of the definition given above. All logarithms in this section have base 2.

LEMMA 6.1 For any node, at most one of its children is heavy. Furthermore, any root to leaf path in a n-node tree contains at most llog nJ light nodes.

DEFINITION 6.4 [Potential Function] A non-root is called right if it is the right child of its parent; it is called left otherwise. The potential of a skew heap is the number of right heavy node it contains. That is, f (H) = number of right heavy nodes in H. We extend the definition of potential function to a collection of skew heaps as follows: f (H1, H2, ··· , Ht) = i=1 f (Hi).

Here is the key result of this chapter.

THEOREM 6.2 Let H1 and H2 be two heaps with n1 and n2 nodes respectively. Let n = n1 + n2. The amortized cost of meld (H1, H2) is O(log n).

Proof Let h1 and h2 denote the number of heavy nodes in the right most paths of H1 and H2 respectively. The number of light nodes on them will be at most llog n1J and llog n2J respectively. Since a node other than root is either heavy or light, and there are two root nodes here that are neither heavy or light, the total number of nodes in the right most paths is at most

In the process of swapping, the h1 + h2 nodes that were right heavy, will lose their status as right heavy. While they remain heavy, they become left children for their parents hence they do not contribute for the potential of the output tree and this means a drop in potential by h1 + h2. However, the swapping might have created new heavy nodes and let us say, the number of new heavy nodes created in the swapping process is h3. First, observe that all these h3 new nodes are attached to the left most path of the output tree. Secondly, by Lemma 6.1, for each one of these right heavy nodes, its sibling in the left most path is a light node. However, the number of light nodes in the left most path of the output tree is less than or equal to llog nJ by Lemma 6.1.

Since insert and delete-min are handled as special cases of meld operation, we conclude

THEOREM 6.3 The amortized cost complexity of all the Meldable Priority Queue operations is O(log n) where n is the number of nodes in skew heap or heaps involved in the operation.