为什么 (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) 来访问正确的数组中的索引。

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

Why (n/2)-1 in heap sort?

java

heapsort