HeapSort算法索引1到n，实际代码必须在0到n-1之间

Question

我对算法比较陌生，想要实现堆排序算法。算法如下：

父(I)返回Math.floor(i/2)

左(I)返回2i

右(I)返回2i+1

然后是恢复heep属性的HEAPIFY方法。算法如下：

HEAPIFY(A, i)
 l = Left(i)
 r = Right(i)
 if (l <= heap-size[A] and A[l] > A[i]
  then largest = l
 else largest = i
 if r <= heap-size[A] and A[r] > A[largest]
  then largest = r
 if largest != i
  then exchange A[i] <-> A[largest]
       HEAPIFY(A, largest)

我实现这个方法的代码是：

public static void HEAPIFY(int[] A, int i) {
    int l = LEFT(i);
    int r = RIGHT(i);
    int largest = 0;
    if (l < A.length && A[l] > A[i]) {
        largest = l;
    } else {
        largest = i;
    }

    if (r < A.length && A[r] > A[largest]) {
        largest = r;
    }

    if (largest != i) {
        int temp = A[i];
        A[i] = A[largest];
        A[largest] = temp;
        HEAPIFY(A, largest);
    }
}

现在我的问题是，算法是通过绘制堆和数组的树来显示的，例如，数组是: 16,14,10,8,7,9,3,2,4,1，对于树和数组，它的索引是从1到n，所以Array1 = 16，编码为Array1= 16。现在我不能调整heapify方法从索引1开始到1，或者以某种方式使它从0开始，让堆从0索引到n-1。

抱歉，如果这是一种困惑，我仍然是困惑，但我真的很感谢一些帮助。

谢谢你们

现在HEAPIFY可以工作了，下面的代码是构建堆的代码：

public static void BUILD_HEAP(int[] A) {
    heapSize = A.length;
    for (int i = (int) Math.floor(A.length / 2.0); i >= 0; i--) {
        HEAPIFY(A, i);
    }
}

构建堆也是可行的，唯一不可行的方法是heapsort。

 public static void HEAPSORT(int[] A) {
    BUILD_HEAP(A);
    for (int i = A.length-1; i >= 1; i--) {
        int temp = A[0];
        A[0] = A[i];
        A[i] = temp;
        heapSize = heapSize-1;
        HEAPIFY(A,0);
    }
}

这必须排序，但当我尝试在调用heapsort之后遍历数组时，它没有给出排序后的数组。有什么办法修复heapsort吗？

Answer 1

如果你想从表单索引1开始，那么你可以像这样初始化数组：-x,16,14,10,8,7,9,3,2,4,1 -x是数组，换句话说，你可以忽略数组中的元素。

如果想要从表单索引0开始，则必须修改函数LEFT(i)和RIGHT(i)。

LEFT(i)返回2*i+1；

右(I)返回2*i+2;

Answer 2

父(I)返回Math.floor(i/2)

返回父级(I) => Math.floor((i - 1) / 2)

左(I)返回2i

=> Left(i)返回2i +1

右(I)返回2i+1

=> Right(i)返回2i +2

你可以通过胡乱摆弄(这就是我实际做的)或者考虑j=i- 1来解决这个问题。

如果i‘=2i且j=i-1，则i=j+1

j‘= i’-1= (2i) -1= (2(j + 1)) -1= 2j +1