A Practical Guide to Data Structures and Algorithms using Java

PriorityQueue

Chapter 27

Pairing Heap Data Structure

package collection.priority

AbstractCollection<E> implements Collection<E>

↑

PairingHeap<E> implements PriorityQueue<E>, Tracked<E>

Uses: Java references and Queue (Chapter 18)

Used By: TaggedPairingHeap (Section 49.8.4)

Strengths: Experimental studies [142, 104] have shown that, in practice, the pairing heap yields

the best performance for many graph algorithms that rely upon a priority queue. (Chapter 56 dis-

cusses the greedy tree builder, from which these algorithms are derived.) In particular, Experiments

by Moret and Shapiro [116] demonstrated that using a pairing heap within Prim’s minimum span- ...