Two new methods for constructing double-ended priority queues from priority queues
Authors:Amr Elmasry, Claus Jensen, and Jyrki Katajainen
Published in:Computing 83,4 (2008), 193-204
Full text:<pdf.gif>PDF (172 kB)  <ps.gif>PS (416 kB)  
DOI:10.1007/s00607-008-0019-2
Copyright:© The Authors
Abstract:

We introduce two data-structural transformations to construct double-ended priority queues from priority queues. To apply our transformations the priority queues exploited must support the extraction of an unspecified element, in addition to the standard priority-queue operations. With the first transformation we obtain a double-ended priority queue which guarantees the worst-case cost of O(1) for find-min, find-max, insert, extract; and the worst-case cost of O(lg n) with at most lg n + O(1) element comparisons for delete. With the second transformation we get a meldable double-ended priority queue which guarantees the worst-case cost of O(1) for find-min, find-max, insert, extract; the worst-case cost of O(lg n) with at most lg n + O(lg lg n) element comparisons for delete; and the worst-case cost of O(min{lg m, lg n}) for meld. Here, m and n denote the number of elements stored in the data structures prior to the operation in question.

Related:<html.gif>HTML (Technical report)  
BibLATEX:
@article{EJK2008bJ,
  author = {Amr Elmasry and Claus Jensen and Jyrki Katajainen},
  title = {Two new methods for constructing double-ended priority queues from
    priority queues},
  journaltitle = {Computing},
  volume = {83},
  number = {4},
  year = {2008},
  pages = {193--204},
}
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 31.12.2011.