Multipartite priority queues
Authors:Amr Elmasry, Claus Jensen, and Jyrki Katajainen
Published in:ACM Transactions on Algorithms 5,1 (2008), Article 14, 19 pp.
Full text:<pdf.gif>PDF (231 kB)  <ps.gif>PS (814 kB)  
Copyright:© ACM
Abstract:We introduce a framework for reducing the number of element comparisons performed in priority-queue operations. In particular, we give a priority queue which guarantees the worst-case cost of O(1) per minimum finding and insertion, and the worst-case cost of O(log n) with at most log n + O(1) element comparisons per deletion, improving the bound of 2 log n + O(1) known for binomial queues. Here, n denotes the number of elements stored in the data structure prior to the operation in question, and log n equals log2(max{2, n}). As an immediate application of the priority queue developed, we obtain a sorting algorithm that is optimally adaptive with respect to the inversion measure of disorder, and that sorts a sequence having n elements and I inversions with at most n log(I / n) + O(n) element comparisons.
Related:<html.gif>HTML (Technical report)  <html.gif>HTML (Later version)  
  author = {Amr Elmasry and Claus Jensen and Jyrki Katajainen},
  title = {Multipartite priority queues},
  journaltitle = {ACM Transactions on Algorithms},
  volume = {5},
  number = {1},
  year = {2008},
  articleno = {14},
  pagetotal = {19},
This page was generated by Jyrki Katajainen <> on 2017-09-26.