Java Reference
In-Depth Information
to be done are the updates after line 28 that indicate a change is in order. If
the vertex has never been placed in the priority queue, we insert it for the
first time, updating its pos data member. Otherwise, we merely call
decreaseKey at line 37.
Whether the binary heap implementation of Dijkstra's algorithm is faster
than the pairing heap implementation depends on several factors. One study
(see the Reference section), suggests that the pairing heap is slightly better
than the binary heap when both are carefully implemented. The results
depend heavily on the coding details and the frequency of the decreaseKey
operations. More study is needed to decide when the pairing heap is suitable
in practice.
summary
In this chapter we described two data structures that support merging and that
are efficient in the amortized sense: the skew heap and the pairing heap. Both
are easy to implement because they lack a rigid structure property. The pair-
ing heap seems to have practical utility, but its complete analysis remains an
intriguing open problem.
In Chapter 24, which is the last chapter, we describe a data structure that
is used to maintain disjoint sets and that also has a remarkable amortized
analysis.
key concepts
pairing heap A structurally unconstrained heap-ordered M -ary tree for which
all operations except deletion take constant worst-case time. Its analysis is
not complete, but it appears to perform well in practice. (876)
skew heap A heap-ordered binary tree without a balancing condition that sup-
ports all operations in logarithmic amortized time. (871)
two-pass merging The order in which the pairing heap subtrees are merged is
important. The simplest algorithm is two-pass merging, in which subtrees
are merged in pairs in a left-to-right scan and then a right-to-left scan is
performed to finish the merging. (878)
common errors
A recursive implementation of the skew heap cannot be used in practice
because the depth of the recursion could be linear.
1.
Be careful not to lose track of the prev links in the skew heap.
2.
 
 
Search WWH ::




Custom Search