Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Toward optimal self-adjusting heaps
Elmasry A. ACM Transactions on Algorithms13 (4):1-14,2017.Type:Article
Date Reviewed: Mar 19 2018

A self-adjusting heap is a heap data structure “that does not [need to] explicitly maintain structural information”; instead, during each access or update operation, the heap is adjusted in a uniform way. Why is a self-adjusting heap, or the self-adjusting version of any other data structure for that matter, interesting? The main advantages of the self-adjustment property are less required space (as no explicit structural information is recorded), ease of implementation, and, perhaps most importantly, better practical performance.

Elmasry has worked in the heap data structures area for a long time; this paper actually completes the preliminary work that appeared in [1,2]. He presents yet another variant of pairing heaps: a self-adjusting version of Fibonacci heaps. The variant presented here achieves the following amortized costs assuming that “n is the number of elements in the resulting heap on which the operation is performed”:

  • O (1) per find-min operation;
  • O (1) per insert operation;
  • O (log log n) per decrease-key operation;
  • O (log log n) per meld operation; and
  • O (log n) per delete-min operation.

Encouragingly, “these bounds are the best known for any self-adjusting heap” and also match the lower bounds (albeit in slightly different settings) established in the literature for a family of pairing heap variants. Additionally, the author shows how meld can have zero amortized cost at the expense of an O (log log n) time increase in the amortized cost for delete-min, where n is the total number of elements in the collection of heaps of the structure.

While the results of this paper are quite interesting and perhaps exciting as well, the author identifies two debatable issues that remain. First, the use of sorting and the necessity to maintain some counters bring up the fundamental question of whether the data structure is really self-adjusting at all. Second, the author does not present an empirical study on this data structure, which sort of questions the motivation of this study since practical superiority has (arguably) been the main drive behind designing self-adjusting data structures.

Reviewer:  M. Sohel Rahman Review #: CR145918 (1806-0319)
1) Elmasry, A. Pairing heaps with O (log log n) decrease cost. In Proc. of SODA '09. SIAM, Philadelphia, PA, 2009, 471–476.
2) Elmasry, A. Pairing heaps with costless meld. In Proc. of ESA '10. Springer, Berlin, 2010, 183–193.
Bookmark and Share
 
Data Structures (E.1 )
 
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
 
Data Storage Representations (E.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Data Structures": Date
Handbook of algorithms and data structures
Gonnet G. (ed), Baeza-Yates R., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991. Type: Book (9780201416077)
Feb 1 1992
Data structures and algorithm analysis
Weiss M., Benjamin-Cummings Publ. Co., Inc., Redwood City, CA, 1992. Type: Book (9780805390544)
Aug 1 1992
Data structures and program design in C
Kruse R., Leung B., Tondo C., Prentice-Hall, Inc., Upper Saddle River, NJ, 1992. Type: Book (9780137256495)
Oct 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy