堆排序的 maxheap 方法，索引为 0 而不是索引 1

Question

我有这个代码heapSort工作正常。我也了解当开始index 1而不是0时，algorithm是如何工作的.我的问题是下面的maxheap方法本身适用于所有大于零的索引，但不适用于索引 0。但是，Sort方法使用 index 0 调用，并且array sorted。当index i = 0时，对maxheap的调用将具有left=2*i=0 and right=2*i+1=1，这导致i和left在0处相同，在index 1处right相同，这意味着root和left相同，只有right树。这让我感到困惑。这是代码：

public class HeapSort 
{    
    private static int heapSize;
    /* Sort Function */
    public static void sort(int arr[])
    {       
        heapify(arr);     
        System.out.println("arrays is "+Arrays.toString(arr));
        for (int i = heapSize; i > 0; i--)
        {
            swap(arr,0, i);
            heapSize = heapSize-1;
            maxheap(arr, 0);
        }
    }     
    /* Function to build a heap */   
    public static void heapify(int arr[])
    {
        heapSize = arr.length-1;
        for (int i = heapSize/2; i >= 0; i--)
            maxheap(arr, i);      
        System.out.println("finished maxheap");
    }
    /* Function to swap largest element in heap */        
    public static void maxheap(int arr[], int i)
    { 
       //heapSize = arr.length-1;// comment this out if you use sort method since `heapSize` is defined at heapfy method
        int left = 2*i ;
        int right = 2*i + 1;
        int max = i;
        if (left <= heapSize && arr[left] > arr[i])
            max = left;
        if (right <= heapSize && arr[right] > arr[max])        
            max = right;
        //System.out.printf("i is %s; left is %s; right is %s; max is %s%n",i,left,right,max);
        if (max != i)
        {
            swap(arr, i, max);
            maxheap(arr, max);
        }
    }    
    /* Function to swap two numbers in an array */
    public static void swap(int arr[], int i, int j)
    {
        //System.out.println("called");
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp; 
    }    
    /* Main method */
    public static void main(String[] args) 
    {
        System.out.println("Heap Sort Testn");
        /* Call method sort */
       int[] arr = {34,5,6,712,90};
        sort(arr);
       System.out.println("nElements after sorting "); 
       System.out.println(Arrays.toString(arr)); 
     /* Call method maxheap; make sure you comment in heapSize=arr.length in the method */
        int[] arr2 = {2,1,3};
        maxheap(arr2, 1);
       //maxheap(arr2,0) will not work, i.e gives same arr2 as output
        System.out.println(Arrays.toString(arr2));
    }    
}

编辑：这两个博客使用相同的代码： sanfoundry.com/java-program-implement-heap-sort, sciencetechpedia.blogspot.com/2012/11/heap-sort-using-java.html

Answer 1

如果数组的起始索引 = 0，则计算左子索引和右子索引的方法应如下所示：

private static int getLeftCh (int index) {
    return index * 2 + 1;
}
private static int getRightCh (int index) {
    return index * 2 + 2;
}

---

[我的堆是这样的]

public class HeapSort {
// Heap sort the givenArray.
// Time complexity = O(nlgn).
// From max to min.
private static int getLeftCh (int index) {
    return index * 2 + 1;
}
private static int getRightCh (int index) {
    return index * 2 + 2;
}
private static void exchange (int[] givenArray, int firstIndex, int secondIndex) {
    int tempElem = givenArray[firstIndex];
    givenArray[firstIndex] = givenArray[secondIndex];
    givenArray[secondIndex] = tempElem;
}
private static void minHeapify (int[] givenArray, int size, int index) {
    int left = getLeftCh(index);
    int right = getRightCh(index);
    int minIndex = index;
    if (left < size && givenArray[left] <= givenArray[index]) minIndex = left;
    else minIndex = index;
    if (right < size && givenArray[right] < givenArray[minIndex]) minIndex = right;
    if (index != minIndex) {
        // Exchange the givenArray[index] and the givenArray[minIndex].
        exchange(givenArray, index, minIndex);
        // Do recrusion on from minIndex.
        minHeapify (givenArray, size, minIndex);
    }
}
private static void buildMinHeap (int[] givenArray) {
    int size = givenArray.length;
    for (int i = (size / 2 - 1); i >= 0; i --) {
        // Do min-heapify on the i.
        minHeapify (givenArray, size, i);
    }
}
public static void heapSortFromMaxToMin (int[] givenArray) {
    int size = givenArray.length;
    // Build the max heap.
    buildMinHeap(givenArray);
    // Do the max-heapify on the remaining part of the minheap.
    for (int i = size - 1; i >= 0; i --) {
        // Move the current first elem back to the last one among the current scope.
        exchange (givenArray, 0, size - 1);
        // Do minHeapify on the remaining part of the heap from the index = 0.
        minHeapify (givenArray, (-- size), 0);
    }
}
// Show array.
public static void showArray (int[] givenArray) {
    int size = givenArray.length;
    for (int i = 0; i < size; i ++)
        System.out.print(String.format("%-6d", givenArray[i]));
    System.out.println();
}

// Main method to test.
public static void main (String[] args) {
    // Test data: {5, 4, 8, 0, 2, -5, 8, 0}.
    int[] givenArray = {5, 4, 8, 0, 2, -5, 8, 0};
    // Test the heap sort on the givenArray, from max to min.
    heapSortFromMaxToMin (givenArray);
    showArray(givenArray);
}
}

Answer 2

当数组从 0 开始时，子节点位于 (2*i)+1 和 (2*i)+2 处。

概括地说，子节点位于 (2*i)+1-array_base 和 (2*i)+2-array_base 。