Smooth heaps and a dual view of self-Adjusting data structures

László Kozma, Thatchaphol Saranurak

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Samenvatting

We present a new connection between self-adjusting binary search trees (BSTs) and heaps, two fundamental, extensively studied, and practically relevant families of data structures (Allen, Munro, 1978; Sleator, Tarjan, 1983; Fredman, Sedgewick, Sleator, Tarjan, 1986; Wilber, 1989; Fredman, 1999; Iacono, Özkan, 2014). Roughly speaking, we map an arbitrary heap algorithm within a broad and natural model, to a corresponding BST algorithm with the same cost on a dual sequence of operations (i.e. the same sequence with the roles of time and key-space switched). This is the first general transformation between the two families of data structures. There is a rich theory of dynamic optimality for BSTs (i.e. the theory of competitiveness between BST algorithms). The lack of an analogous theory for heaps has been noted in the literature (e.g. Pettie; 2005, 2008). Through our connection, we transfer all instance-specific lower bounds known for BSTs to a general model of heaps, initiating a theory of dynamic optimality for heaps. On the algorithmic side, we obtain a new, simple and efficient heap algorithm, which we call the smooth heap. We show the smooth heap to be the heap-counterpart of Greedy, the BST algorithm with the strongest proven and conjectured properties from the literature, widely believed to be instance-optimal (Lucas, 1988; Munro, 2000; Demaine et al., 2009). Assuming the optimality of Greedy, the smooth heap is also optimal within our model of heap algorithms. Intriguingly, the smooth heap, although derived from a non-practical BST algorithm, is simple and easy to implement (e.g. it stores no auxiliary data besides the keys and tree pointers). It can be seen as a variation on the popular pairing heap data structure, extending it with a “power-of-two-choices” type of heuristic. For the smooth heap we obtain instance-specific upper bounds, with applications in adaptive sorting, and we see it as a promising candidate for the long-standing question of a simpler alternative to Fibonacci heaps. The paper is dedicated to Raimund Seidel on occasion of his sixtieth birthday.

Originele taal-2Engels
TitelSTOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
Plaats van productieNew York
UitgeverijAssociation for Computing Machinery, Inc
Pagina's801-814
Aantal pagina's13
ISBN van elektronische versie978-1-4503-5559-9
DOI's
StatusGepubliceerd - 20 jun 2018
Evenement50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, Verenigde Staten van Amerika
Duur: 25 jun 201829 jun 2018

Congres

Congres50th Annual ACM Symposium on Theory of Computing, STOC 2018
LandVerenigde Staten van Amerika
StadLos Angeles
Periode25/06/1829/06/18

Vingerafdruk Duik in de onderzoeksthema's van 'Smooth heaps and a dual view of self-Adjusting data structures'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Kozma, L., & Saranurak, T. (2018). Smooth heaps and a dual view of self-Adjusting data structures. In STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (blz. 801-814). Association for Computing Machinery, Inc. https://doi.org/10.1145/3188745.3188864