algorithm - 构建堆时，堆是否唯一？

Question

我正在研究堆和堆排序。
有一个数组:arr[8] = {6,9,3,1,8,7,2,11}
当我尝试使用代码和铅笔构建堆时，我遇到了两种堆。

使用代码时， 最大堆:11 9 7 6 8 3 2 1

当使用插入理论时，MaxHeap:11 9 7 8 6 3 2 1

我正在使用的代码:

int[] DoHeapSort(int[] value) {
    int length = value.length;

    for (int i = length / 2; i > 0; i--) {
        maxHeapify(value, i, length);
    }

    //print Heap
    for(int i = 0 ; i<value.length; i++)
        System.out.println(value[i]);

    return (value);
}


void maxHeapify(int[] array, int index, int heapSize) {
    int left = index * 2;
    int right = left + 1;
    int max = index;

    if (left <= heapSize && array[left - 1] > array[index - 1]) {
        max = left;
    }

    if (right <= heapSize && array[right - 1] > array[max - 1]) {
        max = right;
    }

    if (max != index) {
        swap(array, index - 1, max - 1);
        maxHeapify(array, max, heapSize);
    }
}

理论，本例中，再创建一个堆数组，从6到11依次插入。 (另一方面，代码是就地堆)

两个 maxHeap 结果都满足堆定义。那么 Heap 不是唯一的吗？谢谢

Answer 1

没错。堆约束(即子代不大于其父代)并未完全指定堆，因此通常有不止一种可能的安排。