Java Reference
In-Depth Information
IN PRACTICE
23.10
Add the public
merge
method to the
PairingHeap
class. Be sure that a
node appears in only one tree.
PROGRAMMING PROBLEMS
23.11
Implement a nonrecursive version of the skew heap algorithm.
Implement the pairing heap algorithm with a
nullNode
sentinel.
23.12
Implement the queue algorithm for
combineSiblings
and compare its
performance with the two-pass algorithm code shown in Figure 23.15.
23.13
If the
decreaseKey
operation is not supported, parent links are not nec-
essary. Implement the pairing heap algorithm without parent links
and compare its performance with the binary heap and/or skew heap
and/or splay tree algorithm.
23.14
The
leftist heap
[1] was the first efficient mergeable priority queue. It is the
worst-case variant of the skew heap suggested in Exercise 23.7. Skew heaps
are described in [6], which also contains solutions to Exercises 23.4 and 23.5.
[3] describes the pairing heap and proves that, when two-pass merging is
used, the amortized cost of all operations is logarithmic. It was long conjec-
tured that the amortized cost of all operations except
deleteMin
is actually
constant and that the amortized cost of the
deleteMin
is logarithmic, so that
any sequence of
D
deleteMin
and
I
other operations takes
O
(
I
+
D
log
N
) time.
However, this conjecture was recently shown to be false [2]. A data structure
that does achieve this bound, but is too complicated to be practical, is the
Fibonacci heap
[4]. The hope is that the pairing heap is a practical alternative
to the theoretically interesting Fibonacci heap, even though its worst case is
slightly worse. Leftist heaps and Fibonacci heaps are discussed in [7].
In [5] is a comparison of various priority queues in the setting of solving
the minimum spanning tree problem (discussed in Section 24.2.2) using a
method very similar to Dijkstra's algorithm.
C. A. Crane, “Linear Lists and Priority Queues as Balanced Binary
Trees,”
Technical Report STAN-CS-72-259,
Computer Science Depart-
ment, Stanford University, Palo Alto, CA, 1972.
1.
M. L. Fredman, “On the Efficiency of Pairing Heaps and Related Data
Structures,”
Journal of the ACM
46
(1999), 473-501.
2.
Search WWH ::
Custom Search