| All-in-one implementation framework for binary heaps | |
| Author: | Jyrki Katajainen |
| Published in: | Software: Practice and Experience 47,4 (2017), 523-558 |
| Full text: |  PDF (485 kB) |
| DOI: | 10.1002/spe.2423 |
| Copyright: | © John Wiley & Sons, Ltd. |
| Abstract: | Even a rough literature review reveals that there are many 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, a framework—a set of class templates—was written that provides a variety of customization options so it could be used to realize a large part of the proposed variants. Also, some of the derived implementations were performance benchmarked. From this work, three 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 and pop. (2) If an array-based solution is sufficient, Williams’ original program from 1964 is still to this day hard to beat. (3) Sometimes a linked structure and clever programming is a viable option. If the binary-heap variant you need is not available at the software library you are using, reading this essay might save you some headaches. |
| Related: |  HTML (Technical report) HTML (Source code) HTML (tar ball) |
| BibLATEX: | @article{Kat2017J,
author = {Jyrki Katajainen},
title = {All-in-one implementation framework for binary heaps},
journaltitle = {Software: Practice and Experience},
volume = {47},
number = {4},
year = {2017},
pages = {523--558},
}
|