Carleton University - School of Computer Science Honours Project
Winter 2022
Implementation and Experimental Comparison of Priority Queue Merge Algorithms
Graydon Haskins
SCS Honours Project Image
ABSTRACT
Standard priority queue operations such as Insert, Remove, FindMin have been extensively studied and many priority queue implementations were first created to optimize for these operations – in fact, some of the first organizations had no consideration for merge whatsoever. However, merge operations have been less often represented in these findings. This project compares various priority queue organizations and algorithms for specific merging/melding performance, first by implementing the merge operations as laid out in their respective papers without specific optimizations, then uses experimental comparison to find out in practice how different priority queue implementations perform at merge operations. The experimental results are differentiated by certain types of workloads, in order to signal for tasks where merge operations are a large factor, if different priority queue organizations perform better than in cases with fewer merges.