Bernard Chazelle
Abstract
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. Its novelty is to beat the logarithmic bound on the complexity of a heap in a comparison-based model. To break this information-theoretic barrier, the entropy of the data structure is reduced by artifically raising the values of certain keys. Given any mixed sequence of n operations, a soft heap with error rate ε (for any 0 < ε ≤ 1/2) ensures that, at any time, at most εn of its items have their keys raised. The amortized complexity of each operation is constant, except for insert, which takes 0(log 1/ε)time. The soft heap is optimal for any value of ε in a comparison-based model. The data structure is purely pointer-based. No arrays are move items across the data structure not individually, as is customary, but in groups, in a data-structuring equivalent of “car pooling.” Keys must be raised as a result, in order to preserve the heap ordering of the data structure. The soft heap can be used to compute exact or approximate medians and percentiles optimally. It is also useful for approximate sorting and for computing minimum spanning trees of general graphs.
- BLUM, M., FLOYD, R. W., PRATT, V., RIVEST, R. L., AND TARJAN, R. E. 1973. Time bounds for selection. J. Comput. Syst. Sci. 7, 448-461.Google Scholar
- CHAZELLE, B. 2000. A minimum spanning tree algorithm with inverse-Ackermann type complexity. J. ACM 47, 6 (Nov.), 000-000. Google Scholar
- FREDMAN, M. L., AND TARJAN, R. E. 1987. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34, 596-615. Google Scholar
- HOFFMAN, K., MEHLHORN, K., ROSENSTIEHL, P., AND TARJAN, R. E. 1986. Sorting Jordan sequences in linear time using level-linked search trees. Inf. Cont. 68, 170-184. Google Scholar
- VUILLEMIN, J. 1978. A data structure for manipulating priority queues. Commun. ACM 21, 309-315. Google Scholar
Index Terms
- The soft heap: an approximate priority queue with optimal error rate
Recommendations
Parallel heap: A practical priority queue for fine-to-medium-grained applications on small multiprocessors
SPDP '95: Proceedings of the 7th IEEE Symposium on Parallel and Distributeed ProcessingWe present an efficient implementation of the parallel heap data structure on a bus-based Silicon Graphics multiprocessor GTX/4D. Parallel heap is theoretically the first heap-based data structure to have implemented an optimally scalable parallel ...
Cache-oblivious shortest paths in graphs using buffer heap
SPAA '04: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architecturesWe present the Buffer Heap (BH), a cache-oblivious priority queue that supports Delete-Min, Delete, and Decrease-Key operations in O(1overB log2 NoverB) amortized block transfers from external memory, where B is the (unknown) block-size and N is the ...
Thin heaps, thick heaps
The Fibonacci heap was devised to provide an especially efficient implementation of Dijkstra's shortest path algorithm. Although asyptotically efficient, it is not as fast in practice as other heap implementations. Expanding on ideas of Høyer [1995], we ...
Reviews
Susan M. Merritt
This paper describes a simple variant of a priority queue, an approximate priority queue, called a soft heap. The soft heap supports the operations: create, insert, delete, meld, and findmin. The authors show that the complexity of a soft heap is better than the logarithmic bound of a heap in a comparison-based model. The soft heap is implemented with pointers, with no arrays and no assumptions about the keys. The soft heap may increase the value of certain keys, which are then referred to as corrupted. Corruption is done by the data structure and the user has no control over it. Findmin, for example, finds the current minimum, which may or may not be corrupted. The benefit of the approach is speed: during heap operations items travel together in something akin to "carpooling" to save time. The authors prove that the soft heap has optimal time bonds in a comparison-based model. They indicate that the soft heap was designed specifically for computing minimum spanning trees; it is a key part of the current fastest deterministic algorithm. They show that soft heaps support dynamic maintenance of percentages in constant amortized time. They explain how soft heaps offer an alternative method for computing medians in linear time. They demonstrate that soft heaps can also do two kinds of approximate sorting. The paper is very well written. The authors describe in detail the soft heap data structure, which is a binomial tree with subtrees possibly missing. They include the actual C code for implementing a soft heap. The set of references is apparently complete. The paper is a good exposition of a very interesting and ingenious data structure and its applications. It is accessible to those who know some computer science.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments