Java Reference
In-Depth Information
recursively merge the tree with the larger root into the right subtree of the tree
with the smaller root.
1
Figure 23.1 shows the effect of this recursive strategy: The right paths of
the two priority queues are merged to form the new priority queue. Each node
on the right path retains its original left subtree, and only the nodes on the
right path are touched. The outcome shown in Figure 23.1 is unattainable by
using only insertions and merges because, as just mentioned, left children
cannot be added by a merge. The practical effect is that what seems to be a
heap-ordered binary tree is in fact an ordered arrangement consisting only of
a single right path. Thus all operations take linear time. Fortunately, a simple
modification ensures that the right path is not always long.
The result is that
right paths are
merged. We must
be careful not to
create unduly long
right paths.
23.1.3
the skew heap: a simple modification
The merge shown in Figure 23.1 creates a temporary merged tree. We can make
a simple modification in the operation as follows. Prior to the completion of a
merge, we swap the left and right children for every node in the resulting right
path of the temporary tree. Again, only those nodes on the original right paths are
on the right path in the temporary tree. As a result of the swap, shown in
Figure 23.2, these nodes then form the left path of the resulting tree. When a
merge is performed in this way, the heap-ordered tree is also called a
skew heap.
To avoid the prob-
lem of unduly long
right paths, we
make the resulting
right path after a
merge
a left path.
Such a merge
results in a
skew
heap.
figure 23.1
Simplistic merging of
heap-ordered trees:
Right paths are
merged.
3
5
3
+
6
8
9
7
6
5
9
7
8
figure 23.2
Merging of skew
heap; right paths are
merged, and the result
is made a left path.
2
4
2
+
3
8
9
5
4
3
6
7
5
9
6
8
7
1. Clearly, either subtree could be used. We arbitrarily use the right subtree.
Search WWH ::
Custom Search