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]\)
Very clear explanation!
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
tools
I am not considering monetization currently.