Wyniki algorytmu Max Heapify

Question

Bawiłem się z niektórymi algorytmami w podręczniku Intro to Algorithms, w szczególności próbuję uzyskać Binary Heap do pracy w 100% poprawnie. Mam dziwne przeczucie, że przykład, z którym pracuję, nie jest poprawny i zastanawiałem się, czy ktoś może pomóc mi wskazać właściwy kierunek.

Biorąc pod tablicą

int[ ] arr = { 1, 2, 3, 4, 7, 8, 9, 10, 14, 16 }; 

Wynik dostaję od MaxHeapify jest

[ 16, 14, 9, 10, 7, 8, 3, 1, 4, 2 ] 

Jednak po wykonaniu pewnej liczby wyszukiwań Google, stwierdziliśmy, że ludzie, którzy używają dokładnie tej tablicy jako przykład oczekiwać wynik będzie następujący:

[ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ] 

Co mnie myli, to wynik, że mój MaxHeapify metoda daje satysfakcję właściwości Heap, ale jest inna niż oczekiwana. Poniżej znajduje się moja implementacja w języku Java:

public static void BuildMaxHeap(int[ ] arr) 
{ 
    for(int i = (int)Math.floor(arr.length - 1); i >= 0; i--) 
     MaxHeapify(arr, i); 
} 
public static void MaxHeapify(int[ ] arr, int i) 
{ 
    int left = 2 * i + 1; 
    int right = 2 * i + 2; 
    int largest = i; 

    if(left < arr.length && arr[ left ] > arr[ largest ]) 
     largest = left; 
    if(right < arr.length && arr[ right ] > arr[ largest ]) 
     largest = right; 
    if(largest != i) 
    { 
     int temp = arr[ i ]; 
     arr[ i ] = arr[ largest ]; 
     arr[ largest ] = temp; 
     MaxHeapify(arr, largest); 
    } 
} 

Answer 1

Stosy, które pokazałeś, są ważne. Nie ma się czym martwić.

Istnieje wiele sposobów zamawiania podwęzłów.

Rozważmy najprostszy przypadek zamianę lewej z prawej strony:

14   14 
10 9 vs 9 10 
... ... ... ... 

Answer 2

Twoje hałdy są niepoprawne. Są różne, ponieważ tablica nie musi być posortowana, gdy nie stosujesz żadnej z tych metod. Do tego właśnie służy Heapsort. Tylko jeden szczegół, w BuildMaxHeap możesz chcieć zmienić

for(int i = (int)Math.floor(arr.length - 1); i >= 0; i--) 

do

for(int i = arr.length/2; i >= 0; i--) 

Dlatego mówię to dlatego, że można zacząć od ostatniego węzła, który ma liści, jak to dzieci, ponieważ liści zawsze są max_heap.