Empirical Analysis of Costless Merge Pairing Heaps
Location
CSU 253/4/5
Start Date
5-4-2010 10:00 AM
End Date
5-4-2010 12:00 PM
Student's Major
Computer Information Science
Student's College
Science, Engineering and Technology
Mentor's Name
Dean Kelley
Mentor's Department
Computer Information Science
Mentor's College
Science, Engineering and Technology
Description
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.
Empirical Analysis of Costless Merge Pairing Heaps
CSU 253/4/5
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.
Recommended Citation
Vander Hook, Joshua. "Empirical Analysis of Costless Merge Pairing Heaps." Undergraduate Research Symposium, Mankato, MN, April 5, 2010.
https://cornerstone.lib.mnsu.edu/urs/2010/poster-session-A/24
