Navigation piles with applications to sorting, priority queues, and priority deques
Authors:Jyrki Katajainen and Fabio Vitale
Published in:Nordic Journal of Computing 10,3 (2003), 238-262
Full text:<ps.gif>PS (370 kB)  
Copyright:© Publishing Association Nordic Journal of Computing

A data structure, named a navigation pile, is described and exploited in the implementation of a sorting algorithm, a priority queue, and a priority deque. When carrying out these tasks, a linear number of bits is used in addition to the elements manipulated, and extra space for a sublinear number of elements is allocated if the grow and shrink operations are to be supported. Our viewpoint is to allow little extra space, make a low number of element moves, and still keep the efficiency in the number of element comparisons and machine instructions. In spite of low memory consumption, the worst-case bounds for the number of element comparisons, element moves, and machine instructions are close to the absolute minimum.

Related:<html.gif>HTML (Errata)  
  author = {Jyrki Katajainen and Fabio Vitale},
  title = {Navigation piles with applications to sorting, priority queues, and
    priority deques},
  journaltitle = {Nordic Journal of Computing},
  volume = {10},
  number = {3},
  year = {2003},
  pages = {238--262},
This page was generated by Jyrki Katajainen <> on 05.02.2013.