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]\)

3 thoughts on “A Beginner’s Guide to Binary Heaps”

  1. I see you don’t monetize devyashis.me, don’t waste
    your traffic, you can earn additional cash every
    month with new monetization method. This is the best adsense alternative for any type of website (they approve all sites),
    for more info simply search in gooogle: murgrabia’s

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.