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 ...
Get A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
