fabianuribe.com/ blog

Data Structures in Javascript: Heaps

The Heap is a great example of how the right data structure can dramatically change the performance of an algorithm, sorting using Heapsort can be achieved in linearithmic time and constant space.

A Heap is a tree-based data structure, it is very efficient executing operations of a priority queue, such as inserts and getting the min/max. A Heap can be classified as a Max Heap or a Min Heap. In order to satisfy the Heap property, in a Max Heap the value on all the parent nodes should be greater than or equal to its children value. On the other hand in a Min Heap the value on all the parent nodes will be less than or equal to its children value.

The implementation

A simple Array allows us to store a Heap without the need of pointers. Where the index for the children of each parent can be obtained:

Left = Parent * 2 + 1
Right = Parent * 2 + 2

The Heap will implement the following basic operations :

The complete source code for this data structure’s including the unit tests for this implementation are included here.

Complexity

Operation Complexity
Sort O(n log n)
Search O(n)
Insert O(log n)
Delete O(log n)
Max/Min O(1)

The Good

The Bad