Improving the efficiency of priority-queue structures: Using data-structural transformations and number systems

Ph.D. Thesis by Claus Jensen

Abstract

In this thesis we investigate the comparison complexity of operations used in the manipulation of worst-case efficient data structures. The focus of the study is on the design and analysis of priority queues and double-ended priority queues. A priority queue is a data structure that stores a collection of elements and supports the operations find-min, insert, extract, decrease, delete, and meld; a double-ended priority queue also supports the operation find-max.

The worst-case efficiency of the priority queues and double-ended priority queues is improved using data-structural transformations and number systems. The research has been concentrated on improving the leading constant in the bound expressing the worst-case comparison complexity of the delete operation while obtaining a constant cost for a subset of the other operations. Our main contributions are:

• We devise a priority queue that for find-min, insert, and delete has a comparison-complexity bound that is optimal up to the constant additive terms, while keeping the worst-case cost of find-min and insert constant
• We introduce a priority queue that for delete has a comparison-complexity bound that is constant-factor optimal (i.e. the constant factor in the leading term is optimal), while keeping the worst-case cost of find-min, insert, and decrease constant
• We describe two new data-structural transformations to construct double-ended priority queues from priority queues
• We introduce three new number systems

The following files are available for download:

• The thesis
• The presentation from the oral defence

This page in Danish