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

László Kozma, Thatchaphol Saranurak

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationSTOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Pages1102-1114
Number of pages13
ISBN (Electronic)978-1-4503-5559-9
DOIs
Publication statusPublished - 20 Jun 2018
Event50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States
Duration: 25 Jun 201829 Jun 2018

Conference

Conference50th Annual ACM Symposium on Theory of Computing, STOC 2018
CountryUnited States
CityLos Angeles
Period25/06/1829/06/18

Fingerprint

Data structures
Sorting
Costs

Keywords

  • Binary search trees
  • Heaps
  • Self-adjusting data structures
  • Sorting

Cite this

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 (pp. 1102-1114). New York: Association for Computing Machinery, Inc. https://doi.org/10.1145/3188745.3188864
Kozma, László ; Saranurak, Thatchaphol. / Smooth heaps and a dual view of self-Adjusting data structures. STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. New York : Association for Computing Machinery, Inc, 2018. pp. 1102-1114
@inproceedings{15744aec60824a97a6cbad419a0177ae,
title = "Smooth heaps and a dual view of self-Adjusting data structures",
abstract = "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, {\"O}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.",
keywords = "Binary search trees, Heaps, Self-adjusting data structures, Sorting",
author = "L{\'a}szl{\'o} Kozma and Thatchaphol Saranurak",
year = "2018",
month = "6",
day = "20",
doi = "10.1145/3188745.3188864",
language = "English",
pages = "1102--1114",
booktitle = "STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing",
publisher = "Association for Computing Machinery, Inc",
address = "United States",

}

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. Association for Computing Machinery, Inc, New York, pp. 1102-1114, 50th Annual ACM Symposium on Theory of Computing, STOC 2018, Los Angeles, United States, 25/06/18. https://doi.org/10.1145/3188745.3188864

Smooth heaps and a dual view of self-Adjusting data structures. / Kozma, László; Saranurak, Thatchaphol.

STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. New York : Association for Computing Machinery, Inc, 2018. p. 1102-1114.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

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

AU - Kozma, László

AU - Saranurak, Thatchaphol

PY - 2018/6/20

Y1 - 2018/6/20

N2 - 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.

AB - 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.

KW - Binary search trees

KW - Heaps

KW - Self-adjusting data structures

KW - Sorting

UR - http://www.scopus.com/inward/record.url?scp=85049889551&partnerID=8YFLogxK

U2 - 10.1145/3188745.3188864

DO - 10.1145/3188745.3188864

M3 - Conference contribution

AN - SCOPUS:85049889551

SP - 1102

EP - 1114

BT - STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

PB - Association for Computing Machinery, Inc

CY - New York

ER -

Kozma L, Saranurak T. 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. New York: Association for Computing Machinery, Inc. 2018. p. 1102-1114 https://doi.org/10.1145/3188745.3188864