Merging priority queues - Data Structures and Problem Solving Using Java - page 884

figure 23.13
The compareAndLink
method merges two
trees

S

F

C

F > S

B

F S

A

+

C

F

A B

S

C

A

F - S

B

the chapter, the subheap with the larger root is made a leftmost child of the
other subheap, the code for which is shown in Figure 23.14. Note that in sev-
eral instances a link reference is tested against null before it accesses its prev
data member. This action suggests that having a nullNode sentinel—as was
customary in the advanced search tree implementations—might be useful.
This possibility is left for you to explore as Exercise 23.12.
Finally, Figure 23.15 implements combineSiblings . We use the array
treeArray to store the subtrees. We begin by separating the subtrees and stor-
ing them in treeArray , using the loop at lines 16 to 22. Assuming that we have
more than one sibling to merge, we make a left-to-right pass at lines 28 and
29. The special case of an odd number of trees is handled at lines 31-36. We
finish the merging with a right-to-left pass at lines 40 and 41. Once we have
finished, the result appears in array position 0 and can be returned.

23.2.3 application: dijkstra's shortest
weighted path algorithm

As an example of how the decreaseKey operation is used, we rewrite Dijkstra's
algorithm (see Section 14.3). Recall that at any point we are maintaining a
priority queue of Path objects, ordered by the dist data member. For each ver-
tex in the graph, we needed only one Path object in the priority queue at any
instant, but for convenience we had many. In this section, we rework the code
so that if a vertex w 's distance is lowered, its position in the priority queue is
found, and a decreaseKey operation is performed for its corresponding Path
object.
The new code is shown in Figure 23.16, and all the changes are rela-
tively minor. First, at line 6 we declare that pq is a pairing heap rather than a
binary heap. Note that the Vertex object has an additional data member pos

The decreaseKey
operation is an
improvement for
Dijkstra's algorithm
in instances for
which there are
many calls
to it.