TY - GEN
T1 - Car-pooling as a data structuring device
T2 - 6th Annual European Symposium on Algorithms, ESA 1998
AU - Chazelle, Bernard
N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 1998
Y1 - 1998
N2 - A simple variant of a priority queue, called a soft heap, is introduced. The data structure supports the usual operations: insert, delete, meld, and findmin. In order to beat the standard information-theoretic bounds, the soft heap allows errors: occasionally, the keys of certain items are artificially raised. Given any 0 < ε < 1/2 and any mixed sequence of n operations, the soft heap ensures that at most εn keys are raised at any time. The amortized complexity of each operation is constant, except for insert, which takes O(log 1/ε) time. The soft heap is optimal. Also, being purely pointer-based, no arrays are used and no numeric assumptions are made on the keys. The novelty of the data structure is that items are moved together in groups, in a data-structuring equivalent of "car pooling." The main application of the data structure is a faster deterministic algorithm for minimum spanning trees.
AB - A simple variant of a priority queue, called a soft heap, is introduced. The data structure supports the usual operations: insert, delete, meld, and findmin. In order to beat the standard information-theoretic bounds, the soft heap allows errors: occasionally, the keys of certain items are artificially raised. Given any 0 < ε < 1/2 and any mixed sequence of n operations, the soft heap ensures that at most εn keys are raised at any time. The amortized complexity of each operation is constant, except for insert, which takes O(log 1/ε) time. The soft heap is optimal. Also, being purely pointer-based, no arrays are used and no numeric assumptions are made on the keys. The novelty of the data structure is that items are moved together in groups, in a data-structuring equivalent of "car pooling." The main application of the data structure is a faster deterministic algorithm for minimum spanning trees.
UR - http://www.scopus.com/inward/record.url?scp=84896777119&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84896777119&partnerID=8YFLogxK
U2 - 10.1007/3-540-68530-8_3
DO - 10.1007/3-540-68530-8_3
M3 - Conference contribution
AN - SCOPUS:84896777119
SN - 3540648488
SN - 9783540648482
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 35
EP - 42
BT - Algorithms, ESA 1998 - 6th Annual European Symposium, Proceedings
PB - Springer Verlag
Y2 - 24 August 1998 through 26 August 1998
ER -