Empirical Analysis of Costless Merge Pairing Heaps
Joshua Vander Hook · Cornerstone (Minnesota State University, Mankato) · 2010
Pairing heaps are a family of data structures that have found wide use in networking and other applications. They are popular because of their ease of implementation, but a complete theoretical analysis is still an open question. Introduced in 2009, the Costless Merge Pairing Heap boasted a potential for increased performance over the original Pairing Heap. To validate the claim of increased performance, the new Costless Merge variant was tested against the original Pairing Heap (both two-pass and multipass variants). Tests included heap-sorting of large data sets and the Hold Model, which is used to simulate a fixed-size queue of discrete events.