堆排序：为什么第 2 层到最后一层的最右侧节点位于索引 n/2-1？

Question

我正在研究用于堆排序的 BST 树。

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

它表明，树的第 2 个最后一级索引的最右边节点总是n/2-1。

请谁能告诉我简单的数学证明。谢谢

Answer 1

为什么第 2 层到最后一层的最右侧节点在 index 处n/2-1？

不是。heapify 算法从堆中第一个有子节点的节点开始。所以在示例堆中，heapify 算法从标记为 17 的节点开始。

假设从零开始索引（意味着根节点在索引 0 处），i第 th 节点的父节点是(i-1)/2。因此，如果n传递给函数的是节点数，则最后一个节点的索引为 ，最后一个节点n-1的父节点((n-1)-1)/2与 相同n/2 - 1。