0

我对算法有点陌生，想实现堆排序算法。算法如下：

Parent(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，因此 Array[1] = 16 和编码 Array[0] = 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);
    }
}

构建堆也有效，唯一不起作用的方法是堆排序。

 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 后尝试遍历数组时，它不会给出排序后的数组。任何想法如何修复堆排序？

4

2 回答 2

1

Parent(i) 返回 Math.floor(i/2)

=> Parent(i) 返回 Math.floor((i - 1) / 2)

左（i）返回 2i

=> 左（i）返回 2i + 1

右(i) 返回 2i+1

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

您可以通过摆弄（这就是我实际上所做的）或考虑 j = i - 1 来解决这个问题。

如果 i' = 2 i 和 j = i - 1 所以 i = j + 1

j' = i' - 1 = (2i) - 1 = (2(j + 1)) - 1 = 2j + 1

于 2012-06-21T03:53:39.987 回答
0

if you want to start form index 1,then you can initialize the array like this: [-x,16,14,10,8,7,9,3,2,4,1] -x is the array[0],in other words,you can ignore the element which is in array[0].

if you want to start form index 0,then you have to modify the function LEFT(i) and RIGHT(i).

LEFT(i) return 2*i+1;

RIGHT(i) return 2*i+2;

于 2012-06-21T05:12:37.983 回答