A pointer-free data structure for merging heaps and min-max heaps. (English) Zbl 0739.68023
A data structure is introduced which makes it possible to represent different instances of mergeable priority queues and dequeues within the same array and at the same time. A pointer-free data structure is developed for mergeable heaps and min-max heaps under which the basic operations of Deletemax, Deletemin, Findmax, Findmin, Merge, Newheap and Deleteheap are performed in \(O(1)\) amortized time for each operation and an Insert operation in \(O(\log n)\) time.
Reviewer: J.Błazewicz (Poznań)
Software:
heapsortReferences:
| [1] | Alt, H.; Mehlhorn, K.; Munro, J. I., Partial match retrieval in implicit data structures, Inform. Process. Lett., 19, 2 (1984) · Zbl 0549.68033 |
| [2] | Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The design and analysis of computer algorithms (1974), Addison-Wesley: Addison-Wesley Reading, Ma · Zbl 0207.01701 |
| [3] | Atkinson, M. D.; Sack, J. R.; Santoro, N.; Strothotte, T., Min-Max heaps and generalized priority queues, Comm. ACM, 29, 10 (1986) · Zbl 0642.68055 |
| [4] | Borodin, A.; Guibas, L. J.; Lynch, N. A.; Yao, A. C., Efficient searching using partial ordering, Inform. Process. Lett., 12, 2 (1981) · Zbl 0457.68056 |
| [5] | Borodin, A.; Fich, F. E.; Meyer auf der Heide, F.; Upfal, E.; Wigderson, A., A tradeoff between search and update time for the implicit dictionary problem, 13th ICALP (1986), Rennes, France · Zbl 0594.68056 |
| [6] | Bentley, J. L.; Saxe, J. B., Decomposable searcing problems I. Static to dynamic transformation, J. Algorithms, 1 (1980) |
| [7] | Carlsson, S.; Munro, J. I.; Poblete, P. V., An implicit binomial queue with constant insertion time, (Proc. SWAT 88, LNCS 318 (1988), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0651.68037 |
| [8] | Cheriton, D.; Tarjan, R. E., Finding minimum spanning trees, SIAM J. Comput., 5, 4 (1976) · Zbl 0358.90069 |
| [9] | Frederickson, G. N., Implicit data structures for the dictionary problem, J. Assoc. Comput. Mach., 30, 1 (1983) · Zbl 0497.68032 |
| [10] | Frederickson, G. N., Recursively rotated orders and implicit data structures: a lower bound, Theoret. Comput. Sci., 29, 1 (1984) · Zbl 0537.68060 |
| [11] | Fredman, M. L.; Tarjan, R. E., Fibonacci heaps and their uses in improved network optimization algorithms, J. Assoc. Comput. Mach., 34, 3 (1987) · Zbl 1412.68048 |
| [12] | Knuth, D. E., The art of computer programming, sorting and searching, Vol. 3 (1973), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0302.68010 |
| [13] | Munro, J. I.; Suwanda, H., Implicit data structures for fast search and updata, J. Comput. System Sci., 21, 2 (1980) · Zbl 0446.68045 |
| [14] | Munro, J. I., An implicit data structure supporting insertion, deletion and search in \(O(lg^2n)\) time, J. Comput. System Sci., 33, 1 (1986) · Zbl 0625.68044 |
| [15] | Sack, J. R.; Strothotte, T., An algorithm for merging heaps, Acta Inform., 22 (1985) · Zbl 0545.68027 |
| [16] | Tarjan, R. E., Data Structures and Network Algorithms, CBMS-NSF Regional Conf. Ser. in Appl. Math., 44 (1983) · Zbl 0584.68077 |
| [17] | Tarjan, R. E., Amortized Computational Complexity, SIAM J. Algebraic Discrete Methods, 6, 2 (1985) · Zbl 0599.68046 |
| [18] | Vuillemin, J., A data structure for manipulating priority queues, Comm. ACM, 21 (1978) · Zbl 0371.68011 |
| [19] | Williams, J. W.J., Algorithm 232: Heapsort, Comm. ACM, 7 (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.
