构建堆时,堆是否唯一？

Question

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

使用代码时,MaxHeap: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

那是对的.堆约束(即子节点不大于它们的父节点)不完全指定堆,因此通常存在多个可能的排列.

Answer 2

考虑项目{1, 2, 3}。最大堆有两种有效的安排：

    3              3
  /   \          /   \
 1     2        2     1

{3, 1, 2}      {3, 2, 1}

这两者都满足有效最大堆的必要条件。

给定一个完整的堆（即所有级别都已满），您可以交换任何节点的子节点并且仍然拥有一个有效的堆。或者，更一般地说，只要保持 shape 属性，就可以交换任何节点的子节点。

请注意，“交换子项”意味着交换锚定在该子项上的整个子树。

除了交换子节点之外，您还可以重新排列节点。

例如，考虑这个最大堆：

      10
    /    \
   9      8
  / \    / \
 7   6  5   4

最后一层节点的顺序无关紧要；任何一个叶节点都可以是 8 或 9 的子节点。这四个子节点有 24 种可能的排列。

其他安排也是可能的。例如：{10,9,6,7,8,5,4}。

你得到的安排取决于你的插入和删除算法的细节，以及插入和删除的顺序。或者，在从数组构建堆的情况下（即 O(n) 方法），开始时数组中项目的顺序。