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.
Originalsprog | Engelsk |
---|---|
Titel | Fun with Algorithms : 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings |
Redaktører | Paolo Boldi, Luisa Gargano |
Antal sider | 10 |
Forlag | Springer |
Publikationsdato | 2010 |
Sider | 156-165 |
ISBN (Trykt) | 978-3-642-13121-9 |
ISBN (Elektronisk) | 978-3-642-13122-6 |
DOI | |
Status | Udgivet - 2010 |
Begivenhed | 5th International Conference on Fun with Algorithms - Ischia, Italien Varighed: 2 jun. 2010 → 4 jun. 2010 Konferencens nummer: 5 |
Konference
Konference | 5th International Conference on Fun with Algorithms |
---|---|
Nummer | 5 |
Land/Område | Italien |
By | Ischia |
Periode | 02/06/2010 → 04/06/2010 |
Navn | Lecture notes in computer science |
---|---|
Vol/bind | 6099 |
ISSN | 0302-9743 |