The magic of a number system

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

*Corresponding author af dette arbejde

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review

2 Citationer (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 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.

OriginalsprogEngelsk
TitelFun with Algorithms : 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings
RedaktørerPaolo Boldi, Luisa Gargano
Antal sider10
ForlagSpringer
Publikationsdato2010
Sider156-165
ISBN (Trykt)978-3-642-13121-9
ISBN (Elektronisk)978-3-642-13122-6
DOI
StatusUdgivet - 2010
Begivenhed5th International Conference on Fun with Algorithms - Ischia, Italien
Varighed: 2 jun. 20104 jun. 2010
Konferencens nummer: 5

Konference

Konference5th International Conference on Fun with Algorithms
Nummer5
Land/OmrådeItalien
ByIschia
Periode02/06/201004/06/2010
NavnLecture notes in computer science
Vol/bind6099
ISSN0302-9743

Citationsformater