×

The weak-heap data structure: variants and applications. (English) Zbl 1257.68059

Summary: The weak heap is a priority queue that was introduced as a competitive structure for sorting. Its array-based form supports the operations find-min in \(O(1)\) worst-case time, and insert and delete-min in \(O(\lg n)\) worst-case time using at most \(\lceil \lg n\rceil\) element comparisons. Additionally, its pointer-based form supports delete and decrease in \(O(\lg n)\) worst-case time using at most \(\lceil \lg n\rceil\) element comparisons.
In this paper we enhance this data structure as follows: 1.) We improve the array-based form to support insert in \(O(1)\) amortized time. The main idea is to temporarily store the inserted elements in a buffer, and, once the buffer is full, to move its elements to the heap using an efficient bulk-insertion procedure. As an application, we use this variant in the implementation of adaptive heapsort. Accordingly, we guarantee, for several measures of disorder, that the formula expressing the number of element comparisons performed by the algorithm is optimal up to the constant factor of the high-order term. Unlike other previous constant-factor-optimal adaptive sorting algorithms, adaptive heapsort relying on the developed priority queue is practically workable.
2.) We improve the pointer-based form to support insert and decrease in \(O(1)\) worst-case time per operation. The expense is that delete then requires at most \(2\lceil \lg n\rceil\) element comparisons, but this is still better than the \(3\lceil \lg n\rceil\) bound known for run-relaxed heaps. The main idea is to allow some nodes to violate the weak-heap ordering; we call the resulting priority queue a relaxed weak heap. We also develop a more efficient amortized variant that provides delete guaranteeing an amortized bound of \(1.5\lceil \lg n\rceil\) element comparisons, which is better than the \(2\lceil \log_{\phi} n\rceil\) bound known for Fibonacci heaps, where \(\phi \) is the golden ratio.
As an application, we use this variant in the implementation of Dijkstra’s shortest-paths algorithm. Experimental results indicate that weak heaps are practically efficient; they are competitive with other priority-queue structures when considering the number of element comparisons performed, and lose by a small margin when considering the actual running time.

MSC:

68P05 Data structures
68P10 Searching and sorting

Software:

LEDA; Quicksort; heapsort
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brodal, G. S.; Fagerberg, R.; Moruz, G., Cache-aware and cache-oblivious adaptive sorting, (Proceedings of the 32nd International Colloquium on Automata, Languages and Programming. Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 3580 (2005), Springer-Verlag), 576-588 · Zbl 1085.68574
[2] Brodal, G. S.; Fagerberg, R.; Moruz, G., On the adaptiveness of quicksort, ACM Journal of Experimental Algorithmics, 12 (2008), Article 3.2 · Zbl 1365.68190
[3] Brown, M. R., Implementation and analysis of binomial queue algorithms, SIAM Journal on Computing, 7, 298-319 (1978) · Zbl 0379.68023
[4] Bruun, A.; Edelkamp, S.; Katajainen, J.; Rasmussen, J., Policy-based benchmarking of weak heaps and their relatives, (Proceedings of the 9th International Symposium on Experimental Algorithms. Proceedings of the 9th International Symposium on Experimental Algorithms, Lecture Notes in Computer Science, vol. 6049 (2010), Springer-Verlag), 424-435
[5] Cherkassky, B. V.; Goldberg, A. V.; Radzik, T., Shortest paths algorithms: Theory and experimental evaluation, Mathematical Programming, 73, 129-174 (1996) · Zbl 0853.90111
[6] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2009), MIT Press · Zbl 1187.68679
[7] Dijkstra, E. W., A note on two problems in connexion with graphs, Numerische Mathematik, 1, 269-271 (1959) · Zbl 0092.16002
[8] Driscoll, J. R.; Gabow, H. N.; Shrairman, R.; Tarjan, R. E., Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation, Communications of the ACM, 31, 1343-1354 (1988)
[9] Dutton, R. D., Weak-heap sort, BIT, 33, 372-381 (1993) · Zbl 1408.68043
[10] Edelkamp, S.; Stiegeler, P., Implementing heapsort with \(n \log n - 0.9 n\) and quicksort with \(n \log n + 0.2 n\) comparisons, ACM Journal of Experimental Algorithmics, 7 (2002) · Zbl 1075.68672
[11] Edelkamp, S.; Wegener, I., On the performance of weak-heapsort, (Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science. Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 1770 (2000), Springer-Verlag), 254-266 · Zbl 0971.68620
[12] Elmasry, A., Adaptive sorting with AVL trees, (Exploring New Frontiers of Theoretical Informatics. Exploring New Frontiers of Theoretical Informatics, IFIP Advances in Information and Communication Technology, vol. 155 (2004), Springer), 315-324 · Zbl 1066.68030
[13] Elmasry, A.; Hammad, A., Inversion-sensitive sorting algorithms in practice, ACM Journal of Experimental Algorithmics, 13 (2009), Article 1.11 · Zbl 1284.68714
[14] Elmasry, A.; Jensen, C.; Katajainen, J., Multipartite priority queues, ACM Transactions on Algorithms, 5 (2008), Article 14 · Zbl 1445.68065
[15] Elmasry, A.; Jensen, C.; Katajainen, J., Two-tier relaxed heaps, Acta Informatica, 45, 193-210 (2008) · Zbl 1144.68015
[16] Fredman, M. L.; Sedgewick, R.; Sleator, D. D.; Tarjan, R. E., The pairing heap: A new form of self-adjusting heap, Algorithmica, 1, 111-129 (1986) · Zbl 0611.68042
[17] Fredman, M. L.; Tarjan, R. E., Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM, 34, 596-615 (1987) · Zbl 1412.68048
[18] Gabow, H. N.; Bentley, J. L.; Tarjan, R. E., Scaling and related techniques for geometry problems, (Proceedings of the 16th Annual ACM Symposium on Theory of Computing (1984), ACM), 135-143
[19] Haeupler, B.; Sen, S.; Tarjan, R., Rank-pairing heaps, (Proceedings of the 17th European Symposium on Algorithms. Proceedings of the 17th European Symposium on Algorithms, Lecture Notes in Computer Science, vol. 5757 (2009), Springer-Verlag), 659-670 · Zbl 1256.68049
[20] Hoare, C. A.R., Quicksort, The Computer Journal, 5, 10-16 (1962) · Zbl 0108.13601
[21] Katajainen, J., The ultimate heapsort, (Proceedings of the Computing: the 4th Australasian Theory Symposium. Proceedings of the Computing: the 4th Australasian Theory Symposium, Australian Computer Science Communications, vol. 20 (1998), Springer-Verlag Singapore Pte. Ltd.), 87-95 · Zbl 0951.68506
[22] Knuth, D. E., Sorting and Searching, (The Art of Computer Programming, vol. 3 (1998), Addison Wesley Longman) · Zbl 0883.68015
[23] Levcopoulos, C.; Petersson, O., Splitsort: An adaptive sorting algorithm, Information Processing Letters, 39, 205-211 (1991) · Zbl 0735.68021
[24] Levcopoulos, C.; Petersson, O., Adaptive heapsort, Journal of Algorithms, 14, 395-413 (1993) · Zbl 0781.68045
[25] McDiarmid, C. J.H.; Reed, B. A., Building heaps fast, Journal of Algorithms, 10, 352-365 (1989) · Zbl 0681.68069
[26] Mehlhorn, K.; Näher, S., The LEDA Platform of Combinatorial and Geometric Computing (1999), Cambridge University Press · Zbl 0976.68156
[27] Moffat, A.; Eddy, G.; Petersson, O., Splaysort: Fast, versatile, practical, Software—Practice and Experience, 126, 781-797 (1996)
[28] Musser, D. R., Introspective sorting and selection algorithms, Software—Practice and Experience, 27, 983-993 (1997)
[29] Noshita, K., A theorem on the expected complexity of Dijkstraʼs shortest path algorithm, Journal of Algorithms, 6, 400-408 (1985) · Zbl 0576.68034
[30] G.L. Peterson, A balanced tree scheme for meldable heaps with updates, Technical Report GIT-ICS-87-23, School of Information and Computer Science, Georgia Institute of Technology, 1987.; G.L. Peterson, A balanced tree scheme for meldable heaps with updates, Technical Report GIT-ICS-87-23, School of Information and Computer Science, Georgia Institute of Technology, 1987.
[31] Prim, R. C., Shortest connection networks and some generalizations, Bell System Technical Journal, 36, 1389-1401 (1957)
[32] Saikkonen, R.; Soisalon-Soininen, E., Bulk-insertion sort: Towards composite measures of presortedness, (Proceedings of the 8th International Symposium on Experimental Algorithms. Proceedings of the 8th International Symposium on Experimental Algorithms, Lecture Notes in Computer Science, vol. 5526 (2009), Springer-Verlag), 269-280
[33] Stasko, J. T.; Vitter, J. S., Pairing heaps: Experiments and analysis, Communications of the ACM, 30, 234-249 (1987)
[34] Tarjan, R. E., Data Structures and Network Algorithms (1983), SIAM
[35] Vuillemin, J., A data structure for manipulating priority queues, Communications of the ACM, 21, 309-315 (1978) · Zbl 0371.68011
[36] Vuillemin, J., A unifying look at data structures, Communications of the ACM, 23, 229-239 (1980) · Zbl 0434.68047
[37] Williams, J. W.J., Algorithm 232: Heapsort, Communications of the ACM, 7, 347-348 (1964)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.