Quando si crea heap, l'heap è univoco?

Question

Sto studiando l'heap & ordinamento heap.
C'è una matrice: arr[8] = {6,9,3,1,8,7,2,11}
Quando sto cercando di creare l'heap, utilizzando codice e matita, ho affrontato due tipi di heap.

Quando si utilizza il codice, MaxHeap: 11 9 7 6 8 3 2 1

Usando teoria inserimento, MaxHeap: 11 9 7 8 6 3 2 1

Il codice che i' m utilizzando:

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 questo caso, creare un altro array per cumulo e inserire dal 6 all'11 in ordine. (D'altra parte, il codice è heap sul posto)

Entrambi i risultati maxHeap hanno soddisfatto la definizione dell'heap. Allora Heap non è unico? Grazie

Answer 1

Questo è corretto. Il vincolo dell'heap (che è che i bambini non sono più grandi dei loro genitori) non specifica completamente l'heap, quindi di solito c'è più di un possibile accordo.

Answer 2

Prendere in considerazione gli articoli {1, 2, 3}. Ci sono due disposizioni valide per un max-heap:

3    3 
/ \  / \ 
1  2  2  1 

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

Sia di coloro che soddisfano le condizioni necessarie per un max-heap valido.

Dato un heap completo (ovvero tutti i livelli sono pieni), è possibile scambiare i figli di qualsiasi nodo e avere ancora un heap valido. O, più in generale, è possibile scambiare i figli di qualsiasi nodo fintanto che si mantiene la proprietà della forma.

Nota che "scambiare i bambini" significa scambiare l'intero sottoalbero ancorato a quel bambino.

Oltre a scambiare i bambini, è possibile riorganizzare i nodi.

Si consideri, per esempio, questo max-heap:

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

L'ordine dei nodi nell'ultimo livello è irrilevante; uno qualsiasi dei nodi foglia potrebbe essere un bambino di 8 o 9. Ci sono 24 possibili permutazioni di quei quattro bambini.

Altri accordi sono possibili anche. Ad esempio: {10,9,6,7,8,5,4}.

La disposizione che si ottiene dipende dalle specifiche degli algoritmi di inserimento e rimozione e anche dall'ordine degli inserimenti e delle rimozioni. Oppure, nel caso di costruzione di un heap da un array (ad esempio il metodo O (n)), l'ordine degli elementi nell'array all'avvio.