Two Skew-Binary Numeral Systems and One Application

作者：Elmasry Amr; Jensen Claus; Katajainen Jyrki^*

来源：Theory of Computing Systems, 2012, 50(1): 185-211.

DOI：10.1007/s00224-011-9357-0

• Numeral systems
• Data structures
• Priority queues
• Binary heaps

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.

• 出版日期2012-1