java - 索引为 0 而不是索引 1 的 heapSort 的 maxheap 方法

Question

我有这段 heapSort 的代码，它工作正常。我还了解当起始 index 为 1 而不是 0 时 algorithm 的工作原理。我的问题是下面的 maxheap 方法本身适用于所有大于零的索引，但不适用于索引 0。但是 Sort 方法调用 index 0 并且 array 得到排序。当 index i = 0 时，对 maxheap 的调用将有 left=2*i=0 和 right=2*i+1=1 ，这导致 i 和 left 在 0 和 right 在 index 1 相同>，表示 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 Test\n");
        /* 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;
}

---

[我的 Heapsort 是这样的]

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);
}
}