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.