przywracania stanu sterty w całej sterty

Question

staram się odpowiedzieć na następujące pytanie: programowania

W programie heap.java metoda insert() wstawia nowy węzeł w sterty i zapewnia, że ​​stan sterty jest zachowana. Napisz metodę toss(), która umieszcza nowy węzeł w tablicy stosu bez próby utrzymania stanu stosu. (Być może każdy nowy element można po prostu umieścić na końcu tablicy.) Następnie napisz metodę restoreHeap(), która przywróci stan sterty w całej sterty. Używanie toss() wielokrotnie, a następnie pojedynczego restoreHeap() jest bardziej wydajne niż wielokrotne używanie insert(), gdy duża ilość danych musi być wstawiona w tym samym czasie. Zobacz opis heapsortu dla wskazówek. Aby przetestować swój program, włóż kilka przedmiotów, wrzuć trochę więcej, a następnie przywróć stertę.

Napisałem kod funkcji podrzucania, która pomyślnie wstawia węzeł na końcu i nie modyfikuje stanu sterty. Mam problemy z funkcją restoreHeap i nie mogę tego objąć. Poniżej zamieściłem dwie funkcje.

pełny kod heap.java jest here (zawiera toss() i restoreHeap())

toss() - że na podstawie tego wyłączyć funkcję wkładki

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

restoreHeap() - na podstawie tego, że wyłączenie funkcji trickleUp i otrzymuję komunikat 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() 

Wszelkie pomysły? Pomoc doceniona.

Answer 1

Dam temu szansę. Oto sposób na zrobienie tego, o co prosiłeś, z pewnym wyjaśnieniem.

Ponieważ wiesz, że połowa wszystkich węzłów w stercie to liście, a liść, sam w sobie, jest prawidłową stertą, wystarczy przejść przez drugą połowę węzłów, aby upewnić się, że są również prawidłowe. Jeśli zrobimy to od dołu i od góry, będziemy mogli zachować poprawną strukturę sterty "poniżej", gdy będziemy przechodzić przez stertę. Można to łatwo osiągnąć przez for pętli:

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

Jak restoreHeap realizowanej wtedy? Należy sprawdzić węzeł pod numerem index pod kątem jego elementów potomnych, aby sprawdzić, czy należy przenieść węzeł. Ponieważ upewniamy się, że drzewa poniżej węzła index są stertami, wystarczy przesunąć węzeł index w odpowiednią pozycję. Dlatego przenosimy go na drzewo.

Najpierw musimy zlokalizować dzieci. Ponieważ każdy wiersz w trzech mieć dwa razy tyle węzłów jak rzędzie przed, dzieci mogą być umieszczone tak:

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

Teraz wystarczy porównać wartość childrens przeciwko swojej wartości index węzłów. Jeśli dziecko ma większą wartość, musisz zamienić węzeł index na węzeł podrzędny. Jeśli oba dzieci mają większą wartość, musisz zamienić z dzieckiem o największej wartości z dwóch (aby zachować strukturę sterty po zamianie). Po zamianie węzłów należy ponownie wywołać tę metodę, aby sprawdzić, czy należy przesunąć węzeł index w dół drzewa.

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