堆积时，堆是否独特？ [英] When building heap, is heap unique?

问题描述

我正在学习堆堆排序。

有一个数组： 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; （int i = length / 2; i> 0; i--）{
 maxHeapify（value，i，length）; 
 
 
} 
 
 //打印Heap 
（int i = 0; i< value.length; i ++）
 System.out.println（value [i] ）; 
 
返回（值）; 
} 
 
 
 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]>数组[max  -  1]）{
 max = 
} 
 
 if（max！= index）{
 swap（array，index  -  1，max  -  1）; 
 maxHeapify（array，max，heapSize）; 
} 
} 
  

理论，在这种情况下，为堆创建另一个数组并从6到11按顺序插入。 （另一方面代码是就地堆）

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

解决方案

是正确的。堆约束（这是孩子不比他们的父母大）并不完全指定堆，所以通常有多种可能的安排。

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

解决方案

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.

这篇关于堆积时，堆是否独特？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！