# 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. Kaan says:

Very clear explanation!

2. I see you don’t monetize devyashis.me, don’t waste