All‐in‐one implementation framework for binary heaps. (20th October 2016)

• Record Type: Journal Article
• Authors: Katajainen, Jyrki
• Is Part Of: Software, practice & experience. Volume 47:Number 4(2017)
• Page Start: 523
• Page End: 558
• Publication Date: 2016-10-20
• Subjects: customizable software libraries -- adaptable component frameworks -- data structures -- binary heaps -- generic programming -- benchmarking; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2423
• Languages: English
• ISSNs: 0038-0644

Abstract

Summary: 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 | 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 perpush andpop . (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. Copyright © 2016 John Wiley & Sons, Ltd.