A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Arrays as Heaps

Because finding the last node is so critical to the heap’s operations, and 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 will now see that we can also use an array to implement a heap. That is, 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 ...