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

chapter 23

merging
priority queues

I n this chapter we examine priority queues that support an additional opera-
tion: The merge operation, which is important in advanced algorithm design,
combines two priority queues into one (and logically destroys the originals).
We represent the priority queues as general trees, which simplifies somewhat
the decreaseKey operation and is important in some applications.
In this chapter, we show

How the skew heap —a mergeable priority queue implemented with
binary trees—works.

n

How the pairing heap —a mergeable priority queue based on the
M -ary tree—works. The pairing heap appears to be a practical alter-
native to the binary heap even if the merge operation is not needed.

n

The skew heap is a
heap-ordered
binary tree without
a balancing condi-
tion and supports all
operations in loga-
rithmic amortized
time.

the skew heap

23.1

The skew heap is a heap-ordered binary tree without a balancing condition.
Without this structural constraint on the tree—unlike with the heap or the bal-
anced binary search trees—there is no guarantee that the depth of the tree is