Layered Heap

V.K. Gulakov, K.V. Gulakov

Abstract


The article is devoted to one of the varieties of the binomial heap, a multilevel heap widely used in solving various problems. A brief comparison of it with the most effective pyramidal structures made it possible to formulate the goals of this structure and the ways to achieve them. Unlike the existing ones, the heap is characterized by the minimum complexity order O of the operation of removing the minimum element from the heap due to the reduction in the number of comparison operations. The article discusses various options for implementing a multi-level heap due to some change in binomial trees. The first option assumes the presence of upper, lower levels and a heap storage, due to which compensation of deleted elements occurs and the number of operations to restore the heap at the lower level is reduced. The second implementation involves the abandonment of the store, but instead of binomial trees, similar to binomial F-trees are introduced. The resulting F-Heap allows you to perform the removal and deletion of a minimal element with complexity O. The possibility of further improvement of this structure is shown.

Full Text:

PDF (Russian)

References


Gulakov V.K., Gulakov K.V. Drozhashhaja piramida // International Journal of Open Information Technologies ISSN: 2307-8162 vol. 6, no.1, 2018

Gulakov V.K., Gulakov, K.V. Slabaja piramida // International Journal of Open Information Technologies ISSN: 2307-8162 vol. 6, no.7, 2018

Kormen T., Lejzer Ch., Rivest R. Algoritmy: postroenie i analiz. — 2-e izd. M.: Izdatel'skij dom «Vil'jams», 2007.— S.1296.

Brown M. Implementation and analysis of binomial queue algorithms. SIAM J. Comput. 7 (1978), 298-319.

Brodal G. Fast meldable priority queues. 4th WADS, LNCS 955 (1995), 282-290.

Brodal G. Worst-case efficient priority queues. 7th ACM SODA (1996), 52-58.

Driscoll J., Gabow H., Shairman R., Tarjan R. Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation. Comm. ACM 31(11) (1988), p. 1343-1354.

Elmasry A. Layered Heaps Algorithm Theory - SWAT 2004 p. 212-222

Fredman M., Sedgewick R., Sleator D., Tarjan R. The pairing heap: a new form of self adjusting heap // Algorithmica 1(1) (1986), 111-129.

Fredman M., Tarjan R. Fibonacci heaps and their uses in improved network optimization algorithms. // J. ACM 34(3) (1987), 596-615.

Iacono J. Improved upper bounds for pairing heaps. // 7th SWAT, LNCS 1851 (2000), 32-45.

Kaplan H. Tarjan R. New heap data structures. // TR-597-99, Princeton University. 1999.

Larkin D.H., Sen S., Tarjan R.E. A Back-to-Basics Empirical Study of Priority Queues / 16th Workshop on Algorithm Engineering and Experiments 2014 (ALENEX14) Portland, Oregon, USA 5 January 2014 R. 61-73

Tarjan R. Amortized computational complexity. / SIAM J. Alg. Disc. Meth. 6 (1985), 306-318.

Vuillemin J. A data structure for manipulating priority queues. / Comm. ACM 21(4) (1978), 309-314.


Refbacks

  • There are currently no refbacks.


Abava  Absolutech IT-EDU 2019

ISSN: 2307-8162