| All-in-one implementation framework for binary heaps | |
| Author: | Jyrki Katajainen |
| Publication: | CPH STL Report 2015-1, Department of Computer Science, University of Copenhagen (2015), 51 pp. |
| Full text: |  PDF (489 kB) |
| Abstract: | By a few search-engine queries, it was easy to identify several alternative ways of implementing a binary heap, the fundamental priority-queue structure loved by us all. Which one of these alternatives is the best in practice? The opinions of crowd-pullers and textbook authors are aligned: use an array. Of course, the correct answer is "it depends". To get from opinions to facts, an adaptable component framework was written that provides a variety of customization options so it could be used to realize many of the proposed variants. Also, some of the derived implementations were performance benchmarked. From this work, two conclusions can be drawn: (1) It is difficult to achieve space efficiency and speed at the same time. If n denotes the current number of values in the data structure, ε is a small positive real, ε < 1, and |V| denotes the size of the values of type V in bytes, space efficiency means (1 + ε) |V| n bytes of space, and speed means O(lg n) worst-case time per push (insert) and pop (extract-min). (2) Sometimes a linked structure and clever programming is a viable option. If a binary-heap variant that you would need is not available at the software library you are using, by reading this essay you can be spared from some headaches. |
| Related: |  HTML (Journal article) HTML (Source code) HTML (tar ball) |
| BibLATEX: | @report{Kat2015R,
author = {Jyrki Katajainen},
title = {All-in-one implementation framework for binary heaps},
type = {CPH STL Report},
number = {2015-1},
institution = {Department of Computer Science, University of Copenhagen},
year = {2015},
pagetotal = {51},
}
|