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 |