1st Student's Major
Computer Information Science
1st Student's College
Science, Engineering and Technology
Students' Professional Biography
Joshua Vander Hook is a senior in the Computer Science deptartment. He is interested in data structures, algorithms, and the study of artificial intelligence, specifically motion and goal planning for autonomous robotics. He intends to attend the University of Minnesota for graduate studies.
Mentor's Name
Dean Kelley
Mentor's Email Address
dean.kelley@mnsu.edu
Mentor's Department
Computer Information Science
Mentor's College
Science, Engineering and Technology
Abstract
Most algorithms’ performance is limited by the data structures they use. Internal algorithms then decide the performance of the data structure. This cycle continues until fundamental results, verified by analysis and experiment, prevent further improvement. In this paper I examine one specific example of this. The focus of this work is primarily on a new variant of the pairing heap. I will review the new implementation, compare its theoretical performance, and discuss my original contribution: the first preliminary data on its experimental performance. It is instructive to provide some background information, followed by a formal definition of heaps in 1.1. I also provide a brief overview of existing literature on the design of these data structures in 1.2 and discuss the methods for evaluating these types of structures in 1.3. Full details about the implementation of a pairing heap can be found in 2.2. Ongoing research has produced a variety of different types of heaps, which will be briefly discussed.
Recommended Citation
Vander Hook, Joshua
(2010)
"Verification of Costless Merge Pairing Heaps,"
Journal of Undergraduate Research at Minnesota State University, Mankato: Vol. 10, Article 9.
DOI: https://doi.org/10.56816/2378-6949.1044
Available at:
https://cornerstone.lib.mnsu.edu/jur/vol10/iss1/9
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License