algorithm - data - Cuando se construye un montón, ¿es único el montón?

min heap algorithm

Question

Estoy estudiando la clasificación de montón y montón.
Hay una matriz: arr[8] = {6,9,3,1,8,7,2,11}
Cuando estoy tratando de construir el montón, usando código y lápiz, me enfrenté a dos tipos de montón.

Al usar el código, MaxHeap: 11 9 7 6 8 3 2 1

Al usar la teoría de inserción, MaxHeap: 11 9 7 8 6 3 2 1

El código que estoy usando:

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

La teoría, en este caso, crea otra matriz para el montón e inserta del 6 al 11 en orden. (Por otro lado, el código está en el lugar montón)

Ambos resultados de maxHeap satisfacen la definición del montón. Entonces Heap no es único? Gracias

Answer 1

Eso es correcto. La restricción de montón (que es que los niños no son mayores que sus padres) no especifica completamente el montón, por lo que generalmente hay más de una disposición posible.

Answer 2

Considere los artículos {1, 2, 3} . Hay dos arreglos válidos para un montón máximo:

    3              3
  /   /          /   /
 1     2        2     1

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

Ambas satisfacen las condiciones necesarias para un máximo acumulado válido.

Dado un montón completo (es decir, todos los niveles están completos), puede intercambiar los elementos secundarios de cualquier nodo y aún tener un montón válido. O, de manera más general, puede intercambiar los elementos secundarios de cualquier nodo siempre que mantenga la propiedad de forma.

Tenga en cuenta que "intercambiar los elementos secundarios" significa intercambiar todo el subárbol anclado en ese elemento secundario.

Además de intercambiar niños, puede reorganizar los nodos.

Considere, por ejemplo, este max-heap:

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

El orden de los nodos en el último nivel es irrelevante; cualquiera de los nodos de la hoja podría ser un niño de 8 o 9. Hay 24 posibles permutaciones de esos cuatro niños.

Otros arreglos son posibles, también. Por ejemplo: {10,9,6,7,8,5,4} .

La disposición que se obtiene depende de los detalles de los algoritmos de inserción y eliminación, y también del orden de las inserciones y eliminaciones. O, en el caso de crear un montón de una matriz (es decir, el método O (n)), el orden de los elementos en la matriz cuando comienza.