An in-place priority queue with O(1) Time for Push and lg n + O(1) comparisons for pop

TY - GEN

T1 - An in-place priority queue with O(1) Time for Push and lg n + O(1) comparisons for pop

AU - Edelkamp, Stefan

AU - Elmasry, Amr

AU - Katajainen, Jyrki

N1 - Conference code: 10

PY - 2015

Y1 - 2015

N2 - An in-place priority queue is a data structure that is stored in an array, uses constant extra space in addition to the array elements, and supports the operations top (find-min), push (insert), and pop (delete-min). In this paper we introduce an in-place priority queue, for which top and push take O(1) worst-case time, and pop takes O(lg n) worst-case time and involves at most lg n + O(1) element comparisons, where n denotes the number of elements currently in the data structure. The achieved bounds are optimal to within additive constant terms for the number of element comparisons, hereby solving a long-standing open problem. Compared to binary heaps, we surpass the comparison bound for pop and the time bound for push. Our data structure is similar to a binary heap with two crucial differences: (1) To improve the comparison bound for pop, we reinforce a stronger heap order at the bottom levels of the heap such that the element at any right child is not smaller than that at its left sibling. (2) To speed up push, we buffer insertions and allow O(lg2 n) nodes to violate heap order in relation to their parents.

AB - An in-place priority queue is a data structure that is stored in an array, uses constant extra space in addition to the array elements, and supports the operations top (find-min), push (insert), and pop (delete-min). In this paper we introduce an in-place priority queue, for which top and push take O(1) worst-case time, and pop takes O(lg n) worst-case time and involves at most lg n + O(1) element comparisons, where n denotes the number of elements currently in the data structure. The achieved bounds are optimal to within additive constant terms for the number of element comparisons, hereby solving a long-standing open problem. Compared to binary heaps, we surpass the comparison bound for pop and the time bound for push. Our data structure is similar to a binary heap with two crucial differences: (1) To improve the comparison bound for pop, we reinforce a stronger heap order at the bottom levels of the heap such that the element at any right child is not smaller than that at its left sibling. (2) To speed up push, we buffer insertions and allow O(lg2 n) nodes to violate heap order in relation to their parents.

U2 - 10.1007/978-3-319-20297-6_14

DO - 10.1007/978-3-319-20297-6_14

M3 - Article in proceedings

SN - 978-3-319-20296-9

T3 - Lecture notes in computer science

SP - 204

EP - 218

BT - Computer science - theory and applications

A2 - Beklemishev, Lev D.

A2 - Musatov, Daniil V.

PB - Springer

T2 - International Computer Science Symposium in Russia 2015

Y2 - 13 July 2015 through 17 July 2015

ER -