Two skew-binary numeral systems and one application
Authors:Amr Elmasry, Claus Jensen, and Jyrki Katajainen
Published in:Theory of Computing Systems 50,1 (2012), 185-211
Full text:<pdf.gif>PDF (350 kB)  
DOI:10.1007/s00224-011-9357-0
Copyright:© Springer-Verlag
Abstract:

We introduce two numeral systems, the magical skew system and the regular skew system, and contribute to their theory development. For both systems, increments and decrements are supported using a constant number of digit changes per operation. Moreover, for the regular skew system, the operation of adding two numbers is supported efficiently. Our basic message is that some data-structural problems are better formulated at the level of a numeral system. The relationship between number representations and data representations, as well as operations on them, can be utilized for an elegant description and a clean analysis of algorithms. In many cases, a pure mathematical treatment may also be interesting in its own right. As an application of numeral systems to data structures, we consider how to implement a priority queue as a forest of pointer-based binary heaps. Some of the number-representation features that influence the efficiency of the priority-queue operations include weighting of digits, carry-propagation and borrowing mechanisms.

Keywords. Numeral systems, data structures, priority queues, binary heaps

Related:<html.gif>HTML (Slides)  <html.gif>HTML (Conference paper)  
BibLATEX:
@article{EJK2011aJ,
  author = {Amr Elmasry and Claus Jensen and Jyrki Katajainen},
  title = {Two skew-binary numeral systems and one application},
  journaltitle = {Theory of Computing Systems},
  volume = {50},
  number = {1},
  year = {2012},
  pages = {185--211},
}
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 14.03.2012.