为什么堆排序中是(n/2)-1？

Question

在堆排序中，在 for 循环中重新排列数组时，为什么我们需要 i=n/2-1 并且我检查了 n/2 也按预期工作。

 // Build heap (rearrange array) 
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i); 

相反，我使用如下所示：

// Build heap (rearrange array) 
    for (int i = n / 2; i >= 0; i--) 
        heapify(arr, n, i); 

以下是完整的程序，

// Java program for implementation of Heap Sort 
public class HeapSort { 
public void sort(int arr[]) 
{ 
    int n = arr.length; 

    // Build heap (rearrange array) 
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i); 

    // One by one extract an element from heap 
    for (int i=n-1; i>=0; i--) 
    { 
        // Move current root to end 
        int temp = arr[0]; 
        arr[0] = arr[i]; 
        arr[i] = temp; 

        // call max heapify on the reduced heap 
        heapify(arr, i, 0); 
    } 
} 

// To heapify a subtree rooted with node i which is 
// an index in arr[]. n is size of heap 
void heapify(int arr[], int n, int i) 
{ 
    int largest = i; // Initialize largest as root 
    int l = 2*i + 1; // left = 2*i + 1 
    int r = 2*i + 2; // right = 2*i + 2 

    // If left child is larger than root 
    if (l < n && arr[l] > arr[largest]) 
        largest = l; 

    // If right child is larger than largest so far 
    if (r < n && arr[r] > arr[largest]) 
        largest = r; 

    // If largest is not root 
    if (largest != i) 
    { 
        int swap = arr[i]; 
        arr[i] = arr[largest]; 
        arr[largest] = swap; 

        // Recursively heapify the affected sub-tree 
        heapify(arr, n, largest); 
    } 
} 

/* A utility function to print array of size n */
static void printArray(int arr[]) 
{ 
    int n = arr.length; 
    for (int i=0; i<n; ++i) 
        System.out.print(arr[i]+" "); 
    System.out.println(); 
} 

// Driver program 
public static void main(String args[]) {
    int arr[] = {12, 11, 13, 5, 6, 7}; 
    int n = arr.length; 
    HeapSort ob = new HeapSort(); 
    ob.sort(arr);
    System.out.println("Sorted array");
    printArray(arr); 
} }

Answer 1

高度为

h

的完整二叉堆有

2^h - 1

个元素。其中，闭域

[0, (2^h)/2-1]

内的元素为内部节点（包括根），闭域

[(2^h)/2, 2^h-2]

内的元素为叶节点。叶节点已经是（平凡的）堆。您需要堆化的第一个元素（因为它有一个子元素，这可能会违反堆属性）位于索引

(2^h)/2-1

。

这个属性——最高索引的内部节点略低于中间点——也扩展到不完整的二进制堆。画出几堆，你就会看到图案。

Answer 2

我认为这是基于你对堆的实现。如果堆的根从索引 0 开始，那么它应该是 (n/2 - 1)，但如果堆的根从索引 1 开始，那么它应该是 (n/2)，以访问数组中的正确索引.

Answer 3

如果 n= 数组大小，则 n/2-1 给出除所有叶子之外的所有索引（当 i=n/2-1，i>=0 时）。