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 -