All-in-one implementation framework for binary heaps

TY - JOUR

T1 - All-in-one implementation framework for binary heaps

AU - Katajainen, Jyrki

PY - 2017/4/1

Y1 - 2017/4/1

N2 - 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: (i) 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 |ν| denotes the size of the values of type ν in bytes, space efficiency means (1 + ϵ)|ν|n bytes of space, and speed means O(lgn) worst-case time per push and pop. (ii) If an array-based solution is sufficient, Williams' original program from 1964 is still to this day hard to beat. (iii) 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.

AB - 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: (i) 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 |ν| denotes the size of the values of type ν in bytes, space efficiency means (1 + ϵ)|ν|n bytes of space, and speed means O(lgn) worst-case time per push and pop. (ii) If an array-based solution is sufficient, Williams' original program from 1964 is still to this day hard to beat. (iii) 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.

U2 - 10.1002/spe.2423

DO - 10.1002/spe.2423

M3 - Journal article

SN - 0038-0644

VL - 47

SP - 523

EP - 558

JO - Software - Practice and Experience

JF - Software - Practice and Experience

IS - 4

ER -