M.Sc. Thesis by Claus Jensen
This is a study of the theoretical and practical efficiency of priority queues. The priority queue is an old and well studied data structure on which a great deal of theoretical and practical work has already been done. A priority queue can be realised in many ways, some of the most commonly used data structures for this are binary heaps and binomial queues.
In this thesis the efficiency of priority queues is studied in three separate papers where one is focusing on the theoretical efficiency of priority queues and the other two papers focus on the practical efficiency.
In the first paper studying the practical efficiency of priority queues (An extended truth about heaps) several alternative implementations of in-place d-ary heaps are studied. An experimental evaluation of the implementations and the C++ standard-library heap are performed. The implementations are evaluated using different types of inputs and ordering functions. The results of the experimental evaluation show that no single heapifying strategy has the best performance for all the different types of inputs and ordering functions, but that bottom-up heapifying has a good performance for most types of inputs and ordering functions.
In the second paper studying the practical efficiency of priority queues (An experimental evaluation of navigation piles) three different implementations of navigation pile are studied. The efficiency of the implementations is experimentally evaluated together with two implementations of binary heaps, again different types of inputs and ordering functions have been used. Furthermore, experiments using several different operation-generation models are performed. The experiments show that when element moves are expensive then navigation piles can be an alternative to binary heaps. In addition to the study of the practical efficiency of navigation piles, the first-ancestor technique and a new and simpler way to make static navigation piles dynamic are introduced.
In the third paper (A framework for speeding up priority-queue operations) the theoretical efficiency of priority queues is studied, and a framework for reducing the number of element comparisons performed in priority-queue operations is introduced. The framework gives a priority queue which guarantees the worst-case cost of O(1) per find-min and insert operation, and the worst-case cost of O(log n) with at most log n + O(1) element comparisons per delete-min and delete operation. Here, n denotes the number of elements stored in the data structure prior to the operation in question, and log n equals maximum of the set {1, log2 n}. Furthermore, in addition to the above-mentioned operations, a priority queue that provides decrease (also called decrease-key) is given. This priority queue achieves the worst-case cost of O(1) per find-min, insert, and decrease operation; and the worst-case cost of O(log n) with at most log n + O(log log n) element comparisons per delete-min and delete operation.
The following files are available for download: