Empirical Analysis of Costless Merge Pairing Heaps

Presenter Information

Joshua Vander HookFollow

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.

This document is currently not available here.

Share

COinS
 
Apr 5th, 10:00 AM Apr 5th, 12:00 PM

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