A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

Arrays as Heaps

Because finding the last node is so critical to the heap’s operations, and because we want to make sure that finding the last node is efficient, heaps are usually implemented using arrays.

While until now we always assumed that every tree consists of independent nodes connected to each other with links (just like a linked list), you’ll now see that we can also use an array to implement a heap. The heap itself can be an abstract data type that really uses an array under the hood.

The diagram shows how an array is used to store the values of a heap.

The way this works is that we assign each node to an index within the array. In this diagram, the index of each node is found in a square below the node. If you look carefully, you’ll ...