Java Reference
In-Depth Information
A recursive viewpoint is as follows. If we let L be the tree with the smaller
root and R be the other tree, the following is true.
1.
If one tree is empty, the other can be used as the merged result.
2.
Otherwise, let Temp be the right subtree of L .
3.
Make L 's left subtree its new right subtree.
4.
Make the result of the recursive merge of Temp and R the new left
subtree of L .
We expect the result of the child swapping to be that the length of the
right path will not be unduly large all the time. For instance, if we merge a
pair of long right-path trees, the nodes involved in the path do not reappear on
a right path for quite some time in the future. Obtaining trees that have the
property that every node appears on a right path is still possible, but that can
be done only as a result of a large number of relatively inexpensive merges. In
Section 23.1.4, we prove this assertion rigorously by establishing that the
amortized cost of a merge operation is only logarithmic.
A long right path is
still possible. How-
ever, it rarely occurs
and must be pre-
ceded by many
merges involving
short right paths.
23.1.4 analysis of the skew heap
Suppose that we have two heaps, H 1 and H 2 , and that there are r 1 and r 2
nodes on their respective right paths. Then the time required to perform the
merge is proportional to r 1 + r 2 . When we charge 1 unit for each node on the
right paths, the cost of the merge is proportional to the number of charges.
Because the trees have no structure, all the nodes in both trees may lie on
the right path. This condition would give a
The actual cost of a
merge is the num-
ber of nodes on the
right paths of the
two trees that are
merged.
( N ) worst-case bound for merg-
ing the trees (in Exercise 23.4 you are asked to construct such a tree). As we
demonstrate shortly, the amortized time needed to merge two skew heaps is
O (log N ).
As with the splay tree, we introduce a potential function that cancels the
varying costs of skew heap operations. We want the potential function to
increase by a total of O (log N ) - ( r 1 + r 2 ) so that the total of the merge cost
and potential change is only O (log N ). If the potential is minimal prior to the
first operation, applying the telescoping sum guarantees that the total spent
for any M operations is O ( M log N ), as with the splay tree.
What we need is some potential function that captures the effect of skew
heap operations. Finding such a function is quite challenging. Once we have
found one, however, the proof is relatively short.
Θ
definition: A node is a heavy nodeif the size of its right subtree is larger than the
size of its left subtree. Otherwise, it is a light node;a node is light if its subtrees are
of equal size.
 
Search WWH ::




Custom Search