The magic of a number system

Amr Ahmed Abd Elmoneim Elmasry; Claus Jensen; Jyrki Katajainen

doi:10.1007/978-3-642-13122-6_17

The magic of a number system

Amr Ahmed Abd Elmoneim Elmasry^*, Claus Jensen, Jyrki Katajainen

^*Corresponding author for this work

Department of Computer Science

1 Citation (Scopus)

Abstract

We introduce a new number system that supports increments with a constant number of digit changes. We also give a simple method that extends any number system supporting increments to support decrements using the same number of digit changes. In the new number system the weight of the ith digit is 2 ⁱ-1, and hence we can implement a priority queue as a forest of heap-ordered complete binary trees. The resulting data structure guarantees O(1) worst-case cost per insert and O(lg n) worst-case cost per delete, where n is the number of elements stored.

Original language	English
Title of host publication	Fun with Algorithms : 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings
Editors	Paolo Boldi, Luisa Gargano
Number of pages	10
Publisher	Springer
Publication date	2010
Pages	156-165
ISBN (Print)	978-3-642-13121-9
ISBN (Electronic)	978-3-642-13122-6
DOIs	https://doi.org/10.1007/978-3-642-13122-6_17
Publication status	Published - 2010
Event	5th International Conference on Fun with Algorithms - Ischia, Italy Duration: 2 Jun 2010 → 4 Jun 2010 Conference number: 5

Conference

Conference	5th International Conference on Fun with Algorithms
Number	5
Country/Territory	Italy
City	Ischia
Period	02/06/2010 → 04/06/2010

Series	Lecture notes in computer science
Volume	6099
ISSN	0302-9743

Access to Document

10.1007/978-3-642-13122-6_17

Cite this

The magic of a number system. / Elmasry, Amr Ahmed Abd Elmoneim; Jensen, Claus; Katajainen, Jyrki.

Fun with Algorithms: 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings. ed. / Paolo Boldi; Luisa Gargano. Springer, 2010. p. 156-165 (Lecture notes in computer science, Vol. 6099).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Elmasry, AAAE, Jensen, C & Katajainen, J 2010, The magic of a number system. in P Boldi & L Gargano (eds), Fun with Algorithms: 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings. Springer, Lecture notes in computer science, vol. 6099, pp. 156-165, 5th International Conference on Fun with Algorithms, Ischia, Italy, 02/06/2010. https://doi.org/10.1007/978-3-642-13122-6_17

@inproceedings{f66148a94d0c47b5a37bb46340450db8,

title = "The magic of a number system",

abstract = "We introduce a new number system that supports increments with a constant number of digit changes. We also give a simple method that extends any number system supporting increments to support decrements using the same number of digit changes. In the new number system the weight of the ith digit is 2 i-1, and hence we can implement a priority queue as a forest of heap-ordered complete binary trees. The resulting data structure guarantees O(1) worst-case cost per insert and O(lg n) worst-case cost per delete, where n is the number of elements stored.",

author = "Elmasry, {Amr Ahmed Abd Elmoneim} and Claus Jensen and Jyrki Katajainen",

year = "2010",

doi = "10.1007/978-3-642-13122-6_17",

language = "English",

isbn = "978-3-642-13121-9",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "156--165",

editor = "Paolo Boldi and Luisa Gargano",

booktitle = "Fun with Algorithms",

note = "5th International Conference on Fun with Algorithms ; Conference date: 02-06-2010 Through 04-06-2010",

}

TY - GEN

T1 - The magic of a number system

AU - Elmasry, Amr Ahmed Abd Elmoneim

AU - Jensen, Claus

AU - Katajainen, Jyrki

N1 - Conference code: 5

PY - 2010

Y1 - 2010

N2 - We introduce a new number system that supports increments with a constant number of digit changes. We also give a simple method that extends any number system supporting increments to support decrements using the same number of digit changes. In the new number system the weight of the ith digit is 2 i-1, and hence we can implement a priority queue as a forest of heap-ordered complete binary trees. The resulting data structure guarantees O(1) worst-case cost per insert and O(lg n) worst-case cost per delete, where n is the number of elements stored.

AB - We introduce a new number system that supports increments with a constant number of digit changes. We also give a simple method that extends any number system supporting increments to support decrements using the same number of digit changes. In the new number system the weight of the ith digit is 2 i-1, and hence we can implement a priority queue as a forest of heap-ordered complete binary trees. The resulting data structure guarantees O(1) worst-case cost per insert and O(lg n) worst-case cost per delete, where n is the number of elements stored.

UR - http://www.scopus.com/inward/record.url?scp=79956299127&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-13122-6_17

DO - 10.1007/978-3-642-13122-6_17

M3 - Article in proceedings

AN - SCOPUS:79956299127

SN - 978-3-642-13121-9

T3 - Lecture notes in computer science

SP - 156

EP - 165

BT - Fun with Algorithms

A2 - Boldi, Paolo

A2 - Gargano, Luisa

PB - Springer

T2 - 5th International Conference on Fun with Algorithms

Y2 - 2 June 2010 through 4 June 2010

ER -

The magic of a number system

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this