Heapsort: Why is the right-most node of the 2nd to last level at index n/2-1?

Question

I was studying BST tree for heap sort.

void heapSort(int arr[], int n){
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
    heapify(arr, n, i);  
     -----------
     ----------
}

It shows that,right most node of tree's 2nd last level index is always n/2-1.

Please Can anyone show me simple math proof of that.Thanks

Answer 1

Why is the right-most node of the 2nd to last level at index n/2-1?

It's not. The heapify algorithm starts at the first node in the heap that has children. So in the example heap, the heapify algorithm starts at the node labeled 17.

Assuming zero-based indexing (meaning the root node is at index 0), the parent of the ith node is (i-1)/2. So if the n passed to the function is the number of nodes, then the index of the last node is n-1, and the parent of the last node ((n-1)-1)/2 which is the same as n/2 - 1.

Answer 2

It shows that,right most node of tree's 2nd Last level index is always n/2-1.

I agree with user3386109's correct answer that it's not. From there on, the focus of that answer is the meaning of the index you're printing. In this answer, I'll focus on the index of the last element in the penultimate row (which is what you've explicitly asked).

Assuming 0-based indexing for both nodes and levels, the last node at level i is at index 2^{i + 1} - 2 (this follows from the expression for a geometric sum). So, the last index at level 0 is 0, the last index at level 1 is 2, the last index at level 2 is 6, and so forth.

Now assume the tree has i full levels, and an additional j nodes at the last level. The total number of nodes is n = 2^{i + 1} - 2 + j. Taking a base-2 log and rounding down gives i + 1. Combining with the expression from before, this gives the final answer

2^⌊log(n)⌋ - 2.

Here are some examples:

• For n = 1, the penultimate level is undefined.

• For n = 2, 3, the rounded down log is 1, and the answer is 0.

• For n = 4, 5, 6, 7, the rounded down log is 2, and the answer is 2.