Policy-based benchmarking of weak heaps and their relatives

Asger Bruun; Stefan Edelkamp; Jyrki Katajainen; Jens Rasmussen

doi:10.1007/978-3-642-13193-6_36

Policy-based benchmarking of weak heaps and their relatives

Asger Bruun^*, Stefan Edelkamp, Jyrki Katajainen, Jens Rasmussen

^*Corresponding author for this work

Department of Computer Science

12 Citations (Scopus)

Abstract

In this paper we describe an experimental study where we evaluated the practical efficiency of three worst-case efficient priority queues: 1) a weak heap that is a binary tree fulfilling half-heap ordering, 2) a weak queue that is a forest of perfect weak heaps, and 3) a runrelaxed weak queue that extends a weak queue by allowing some nodes to violate half-heap ordering. All these structures support delete and delete-min in logarithmic worst-case time. A weak heap supports insert and decrease in logarithmic worst-case time, whereas a weak queue reduces the worst-case running time of insert to O(1), and a run-relaxed weak queue that of both insert and decrease to O(1). As competitors to these structures, we considered a binary heap, a Fibonacci heap, and a pairing heap. Generic programming techniques were heavily used in the code development. For benchmarking purposes we developed several component frameworks that could be instantiated with different policies.

Original language	English
Title of host publication	Experimental Algorithms : 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20-22, 2010. Proceedings
Editors	Paola Festa
Number of pages	12
Publisher	Springer
Publication date	2010
Pages	424-435
ISBN (Print)	978-3-642-13192-9
ISBN (Electronic)	978-3-642-13193-6
DOIs	https://doi.org/10.1007/978-3-642-13193-6_36
Publication status	Published - 2010
Event	9th International Symposium on Experimental Algorithms - Napoli, Italy Duration: 20 May 2010 → 22 May 2010

Conference

Conference	9th International Symposium on Experimental Algorithms
Country/Territory	Italy
City	Napoli
Period	20/05/2010 → 22/05/2010

Series	Lecture notes in computer science
Volume	6049
ISSN	0302-9743

Access to Document

10.1007/978-3-642-13193-6_36

Cite this

Bruun, A., Edelkamp, S., Katajainen, J., & Rasmussen, J. (2010). Policy-based benchmarking of weak heaps and their relatives. In P. Festa (Ed.), Experimental Algorithms: 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20-22, 2010. Proceedings (pp. 424-435). Springer. Lecture notes in computer science Vol. 6049 https://doi.org/10.1007/978-3-642-13193-6_36

Policy-based benchmarking of weak heaps and their relatives. / Bruun, Asger; Edelkamp, Stefan; Katajainen, Jyrki et al.

Experimental Algorithms: 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20-22, 2010. Proceedings. ed. / Paola Festa. Springer, 2010. p. 424-435 (Lecture notes in computer science, Vol. 6049).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Bruun, A, Edelkamp, S, Katajainen, J & Rasmussen, J 2010, Policy-based benchmarking of weak heaps and their relatives. in P Festa (ed.), Experimental Algorithms: 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20-22, 2010. Proceedings. Springer, Lecture notes in computer science, vol. 6049, pp. 424-435, 9th International Symposium on Experimental Algorithms, Napoli, Italy, 20/05/2010. https://doi.org/10.1007/978-3-642-13193-6_36

@inproceedings{17fbffc2fc04478dbbb54612d685ab95,

title = "Policy-based benchmarking of weak heaps and their relatives",

abstract = "In this paper we describe an experimental study where we evaluated the practical efficiency of three worst-case efficient priority queues: 1) a weak heap that is a binary tree fulfilling half-heap ordering, 2) a weak queue that is a forest of perfect weak heaps, and 3) a runrelaxed weak queue that extends a weak queue by allowing some nodes to violate half-heap ordering. All these structures support delete and delete-min in logarithmic worst-case time. A weak heap supports insert and decrease in logarithmic worst-case time, whereas a weak queue reduces the worst-case running time of insert to O(1), and a run-relaxed weak queue that of both insert and decrease to O(1). As competitors to these structures, we considered a binary heap, a Fibonacci heap, and a pairing heap. Generic programming techniques were heavily used in the code development. For benchmarking purposes we developed several component frameworks that could be instantiated with different policies.",

author = "Asger Bruun and Stefan Edelkamp and Jyrki Katajainen and Jens Rasmussen",

year = "2010",

doi = "10.1007/978-3-642-13193-6_36",

language = "English",

isbn = "978-3-642-13192-9",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "424--435",

editor = "Paola Festa",

booktitle = "Experimental Algorithms",

note = "9th International Symposium on Experimental Algorithms ; Conference date: 20-05-2010 Through 22-05-2010",

}

TY - GEN

T1 - Policy-based benchmarking of weak heaps and their relatives

AU - Bruun, Asger

AU - Edelkamp, Stefan

AU - Katajainen, Jyrki

AU - Rasmussen, Jens

PY - 2010

Y1 - 2010

N2 - In this paper we describe an experimental study where we evaluated the practical efficiency of three worst-case efficient priority queues: 1) a weak heap that is a binary tree fulfilling half-heap ordering, 2) a weak queue that is a forest of perfect weak heaps, and 3) a runrelaxed weak queue that extends a weak queue by allowing some nodes to violate half-heap ordering. All these structures support delete and delete-min in logarithmic worst-case time. A weak heap supports insert and decrease in logarithmic worst-case time, whereas a weak queue reduces the worst-case running time of insert to O(1), and a run-relaxed weak queue that of both insert and decrease to O(1). As competitors to these structures, we considered a binary heap, a Fibonacci heap, and a pairing heap. Generic programming techniques were heavily used in the code development. For benchmarking purposes we developed several component frameworks that could be instantiated with different policies.

AB - In this paper we describe an experimental study where we evaluated the practical efficiency of three worst-case efficient priority queues: 1) a weak heap that is a binary tree fulfilling half-heap ordering, 2) a weak queue that is a forest of perfect weak heaps, and 3) a runrelaxed weak queue that extends a weak queue by allowing some nodes to violate half-heap ordering. All these structures support delete and delete-min in logarithmic worst-case time. A weak heap supports insert and decrease in logarithmic worst-case time, whereas a weak queue reduces the worst-case running time of insert to O(1), and a run-relaxed weak queue that of both insert and decrease to O(1). As competitors to these structures, we considered a binary heap, a Fibonacci heap, and a pairing heap. Generic programming techniques were heavily used in the code development. For benchmarking purposes we developed several component frameworks that could be instantiated with different policies.

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

U2 - 10.1007/978-3-642-13193-6_36

DO - 10.1007/978-3-642-13193-6_36

M3 - Article in proceedings

AN - SCOPUS:78650652076

SN - 978-3-642-13192-9

T3 - Lecture notes in computer science

SP - 424

EP - 435

BT - Experimental Algorithms

A2 - Festa, Paola

PB - Springer

T2 - 9th International Symposium on Experimental Algorithms

Y2 - 20 May 2010 through 22 May 2010

ER -

Policy-based benchmarking of weak heaps and their relatives

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this