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
references
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