I am trying to understanding the logic behind the left & right values for the minHeapify function.
Why is the index multiplied by 2?
Cheers
Hi Robert ,
This is Maida from Educative.
Initially, elements are placed in nodes in the same order as they appear in the array. Then we call _minHeapify function on all the elements to restore the heap property (starting from the bottom of the heap). The _minHeapify function swaps the values of the parent nodes with the values of their smallest child nodes until the heap property is restored.
In the given code, left and right are the indexes of the left and right child of the heap, respectively, and index is the index of the current parent node. We need to multiply the left and right with 2 because elements of the heap are arranged in this manner:
4, 9, 3, 2, 1, 8, 0
and It would look like this:
From the figure, it is clear that to find the left child, we need to multiply the parent index by 2 and add 1 to it. Since the right child exists right next to it we need to add 2 after multiplying the parent index by 2.
For example, if the parent is at index 3 then the left child will be at 3*2+1=7th index, and the right child will be at 3*2+2=8th index.
We hope Educative has inspired to further your learning.
Best Regards,
Maida | Developer Advocate