Improving the efficiency of priority-queue structures – University of Copenhagen

Improving the efficiency of priority-queue structures

Using data-structural transformations and number systems. PhD thesis defence 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.

In total, we introduce seven priority queues, two double-ended priority queues, and three number systems.

Assessment committee:

Chairman: Associate professor Stephen Alstrup, Department of Computer Science, University of Copenhagen, Denmark

Associate professor Inge Li Gørtz, DTU Informatics, Denmark

Professor Haim Kaplan, School of Computer Science, Tel Aviv University, Israel

Section 15(2) PhD thesis

For an electronic copy of the thesis, please contact Jette Giovanni Møller, jettegm@diku.dk