When building heap, is heap unique?

问题:

I'm studying heap & heap sorting.
There is a array : arr[8] = {6,9,3,1,8,7,2,11}
When I'm trying to build the heap, using code and pencil, I faced two kinds of heap.

When using code, MaxHeap : 11 9 7 6 8 3 2 1

When using insertion theory, MaxHeap : 11 9 7 8 6 3 2 1

The code that i'm using :

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

Theory, in this case, create another array for heap and insert from 6 to 11 in order. (On the other hand, code is in-place heap)

Both maxHeap results satisfied heap definition. Then Heap is not unique ? Thanks

回答1:

That's correct. The heap constraint (which is that children are not greater than their parents) does not completely specify the heap, so there is usually more than one possible arrangement.

回答2:

Consider the items {1, 2, 3}. There are two valid arrangements for a max-heap:

    3              3
  /   \          /   \
 1     2        2     1

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

Both of those satisfy the conditions necessary for a valid max-heap.

Given a full heap (i.e. all levels are full), you can swap the children of any node and still have a valid heap. Or, more generally, you can swap the children of any node as long as you maintain the shape property.

Note that "swap the children" means swapping the entire subtree anchored at that child.

In addition to swapping children, you can rearrange nodes.

Consider, for example, this max-heap:

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

The order of nodes in the last level is irrelevant; any one of the leaf nodes could be a child of either 8 or 9. There are 24 possible permutations of those four children.

Other arrangements are possible, too. For example: {10,9,6,7,8,5,4}.

Which arrangement you get depends on the specifics of your insertion and removal algorithms, and also on the order of insertions and removals. Or, in the case of building a heap from an array (i.e. the O(n) method), the order of items in the array when you start.