Restore condizione mucchio nell'intero mucchio

Question

sto cercando di rispondere alla seguente domanda programmazione:

Nel programma heap.java, il metodo insert() inserisce un nuovo nodo in mucchio e garantisce la condizione mucchio è conservato. Scrivi un metodo toss() che colloca un nuovo nodo nell'array di heap senza tentare di mantenere la condizione di heap. (Forse ogni nuovo elemento può essere semplicemente posizionato alla fine dell'array.) Quindi scrivere un metodo restoreHeap() che ripristina la condizione heap in tutto l'heap. L'utilizzo di toss() ripetutamente seguito da un singolo restoreHeap() è più efficiente rispetto all'utilizzo di insert() ripetutamente quando è necessario inserire una grande quantità di dati alla volta. Vedi la descrizione di heapsort per gli indizi. Per testare il programma, inserire alcuni elementi, aggiungerne altri e quindi ripristinare l'heap.

Ho scritto il codice per la funzione di lancio che inserisce correttamente il nodo alla fine e non modifica la condizione di heap. Sto avendo problemi con la funzione restoreHeap e non riesco a capirlo. Ho incluso le due funzioni di seguito.

il codice completo della heap.java è here (comprende toss() e restoreHeap())

toss() - ho basato questo disattiva la funzione di inserimento

public boolean toss(int key) 
{ 
    if(currentSize==maxSize) 
     return false; 
    Node newNode = new Node(key); 
    heapArray[currentSize] = newNode; 
    currentSize++; 
    return true; 
} // end toss() 

restoreHeap() - ho basato questo disattiva la funzione trickleUp ed io sto ottenendo un StackOverflowError.

public void restoreHeap(int index) 
{ 
    int parent = (index-1)/2; 
    Node bottom = heapArray[index]; 

    while(index > 0 && 
      heapArray[parent].getKey() < bottom.getKey()) 
    { 
     heapArray[index] = heapArray[parent]; // move it down 
     index = parent; 
     parent = (parent-1)/2; 
    } // end while 
    heapArray[index] = bottom; 
    while(index != 0) 
    { 
     restoreHeap(parent++); 
    } 

} // end restoreHeap() 

Qualche idea? Aiuto apprezzato

Answer 1

Farò un tentativo. Ecco un modo per fare ciò che hai chiesto con qualche spiegazione.

Poiché si sa che la metà di tutti i nodi in un heap sono foglie e una foglia, di per sé, è un heap valido, è sufficiente scorrere l'altra metà dei nodi per assicurarsi che anch'essi siano validi. Se lo facciamo dal basso verso l'alto, possiamo mantenere una struttura heap valida "sotto" mentre risaliamo attraverso l'heap. Questo può essere facilmente realizzato da un for ciclo:

public void rebuildHeap() 
{ 
    int half = heapArray.length/2; 
    for(int i = half; i >= 0; i--) 
     restoreHeap(i); 
} 

Come viene attuata restoreHeap allora? Si suppone di controllare il nodo su index contro i suoi figli per vedere se è necessario spostare il nodo. Poiché ci assicuriamo che gli alberi sotto il nodo index siano heap, dobbiamo solo spostare il nodo index nella posizione corretta. Quindi lo spostiamo nell'albero.

Per prima cosa dobbiamo localizzare i bambini. Dal momento che ogni riga del tre hanno il doppio dei nodi come la fila prima, i bambini possono essere posizionati in questo modo:

private void restoreHeap(int index) 
{ 
    int leftChild = (index * 2) + 1; //+1 because arrays start at 0 
    int rightChild = leftChild +1; 
    ... 

Ora devi solo per confrontare il valore dei bambini contro il vostro valore index nodi. Se un bambino ha un valore maggiore, è necessario scambiare il nodo index con il nodo figlio. Se entrambi i bambini hanno un valore maggiore, è necessario scambiare il bambino con il valore maggiore dei due (per mantenere la struttura dell'heap dopo lo scambio). Quando i nodi sono stati scambiati, è necessario chiamare di nuovo il metodo per vedere se è necessario spostare il nodo index più in basso nell'albero.

... 
    int biggest = index; 
    if(leftChild < currentSize && heapArray[leftChild].getKey() > heapArray[index].getKey()) 
     biggest = leftChild; //LeftChild is bigger 
    if(rightChild < currentSize && heapArray[rightChild].getKey() > heapArray[biggest].getKey()) 
     biggest = rightChild; //RightChild is bigger than both leftChild and the index node 

    if(biggest != index) //If a swap is needed 
    { 
     //Swap 
     Node swapper = heapArray[biggest]; 
     heapArray[biggest] = heapArray[index]; 
     heapArray[index] = swapper; 

     restoreHeap(biggest); 
    } 
}