Java Reference
In-Depth Information
Tests to ensure that references are not
null
must be made throughout the
pairing heap code.
3.
When a merge is performed, a node should not reside in two pairing heaps.
4.
The pairing heap class is available, with a test program. Figure 23.16 is part of
the
Graph
class shown in Chapter 14
(Graph.java).
PairingHeap.java
Contains the implementation for the
PairingHeap
class.
IN SHORT
23.1
Show the result of a skew heap built from the insertion sequence
a.
1, 2, 3, 4, 5, 6, 7
b.
4, 3, 5, 2, 6, 7, 1
Show the result of a pairing heap built from the insertion sequence
a.
23.2
1, 2, 3, 4, 5, 6, 7
b.
4, 3, 5, 2, 6, 7, 1
For each heap in Exercises 23.1 and 23.2, show the result of two
deleteMin
operations.
23.3
IN THEORY
23.4
Show that the logarithmic amortized bound for skew heap operations
is not a worst-case bound by giving a sequence of operations that lead
to a
merge
that requires linear time.
Show that both the
decreaseKey
and
increaseKey
operations can be
supported by skew heaps in logarithmic amortized time.
23.5
Describe a linear-time
buildHeap
algorithm for the skew heap.
23.6
Show that storing the length of the right path for each node in the tree
enables you to impose a balancing condition that yields logarithmic
worst-case time per operation. Such a structure is called a
leftist heap
.
23.7
Show that using a stack to implement the
combineSiblings
operation
for pairing heaps is bad. Do so by constructing a sequence that has
linear amortized cost per operation.
23.8
Describe how to implement
increaseKey
for pairing heaps.
23.9
Search WWH ::
Custom Search