Codebox Software

JavaScript Binary Heap

Published:

Here's a simple JavaScript implementation of a Binary Heap, a data structure that can be used as a Priority Queue storing items and returning them in priority order. The code uses a number of ECMAScript 6 features and therefore will not work on older browsers.

I've implemented insert, extract and peek methods because that was all I needed at the time, but it should be simple to extend if required:

MethodTime Complexity (Worst Case)
insert()O(log n)
extract()O(log n)
peek()O(1)

To create a heap object, just call the buildHeap() function and add new items using the insert() method. By default a 'min-heap' is created, where the smallest remaining item will be returned next:

const heap = buildHeap();

heap.insert(3);
heap.insert(2);
heap.insert(1);

heap.extract(); // 1
heap.extract(); // 2
heap.extract(); // 3
heap.extract(); // undefined - heap is now empty

buildHeap() accepts an optional argument which will be used as a mapping function, transforming values before comparing them with each other. In this way custom ordering can be implemented, for example to create a heap which stores objects and always returns the one with the highest score property, do this:

const maxScoreHeap = buildHeap(v => -v.score);