A Beginner’s Guide to Binary Heaps

Representation of Heaps in Memory

While heaps can be visualized as binary trees, implementing them as actual trees is naive. Because they are nearly-complete, it is possible to implement them using arrays. Heaps are laid out in memory in level-order.

Because heaps are laid out in level order when implemented as an array, if we traverse the array from left to right, we traverse the heap’s tree in level-order, going from left to right, then top to bottom. In the image below, the red arrows show the order in which elements are visited:

The root of the tree is the first element in the array: \(\text{root}=\text{arr}[0]\)

The other nodes are found using the following relations:

  • Parent node: \(\text{parent}=\text{arr}[\lfloor\frac{i-1}{2}\rfloor]\)
  • Left child node: \(\text{left child}=\text{arr}[(2\times i)+1]\)
  • Right child node: \(\text{right child}=\text{arr}[(2\times i)+2]\)

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.