MaxHeapify無法正常工作

Question

嗯，我花了超過8個小時的工作。我已經逐字複製了該書中的示例，並試圖在其他資源的基礎上實現堆在線。我仍然無法讓堆工作正確。以下是我迄今編碼：

import static java.lang.System.*; 
import java.util.Random; 
import java.util.Scanner; 

public class Heap{ 

static int[] arr; 
static int heapSize; 
static int max = 0; 

public static void main(String[] args) { 

    Scanner keys = new Scanner(in); 

    out.print("Enter size of heap desired: ");      //Receive input from user regarding 
    int arrSize = keys.nextInt();         //desired heap size 

    ArrayBuild(arrSize);   //Call builder to construct array based on user desired size 

    heapSize = arr.length; 

    int start = arr.length/2-1; 

    MaxHeapify(start); 

    keys.close(); 

} 

public static void ArrayBuild(int size){   //Constructs new array based on given size 
    arr = new int[size]; 

    for(int i=0; i<arr.length; i++) 
     arr[i] = new Random().nextInt(10)+1; 
} 

public static void MaxHeapify(int i){ 

     int left = 2*i; 
     int right = 2*i+1; 

     if(left <= heapSize && arr[left] > arr[i]){ 
      max = left; 
     }else{ 
      max = i; 
     } 

     if(right <= heapSize && arr[right] > arr[max]){ 
      max = right; 
     } 

     if(max != i){ 
      swap(i, max); 
      MaxHeapify(max); 
     } 
} 

public static void BuildMaxHeap(){ 
    for(int i=(arr.length/2); i>0; i--) 
     MaxHeapify(i); 
} 

public static void swap(int i, int max){ 
    int temp = arr[i]; 
    arr[i] = arr[max]; 
    arr[max] = temp; 
} 

}

Answer 1

2個問題：

int left = 2 * i; 
int right = 2 * i + 1; 

應該是：

int left = 2 * i + 1; 
int right = 2 * i + 2; 

Java數組基於這樣的根是0 （這是第一個元素）與您的公式適用於使用基於1的數組的情況。在Java中，左邊的孩子也將0作爲我記憶中的2 * 0 = 0等。

第二次當您在main()中構建堆時，您需要運行MaxHeapify()，以獲取像你在做的一半元素BuildMaxHeap()，不僅爲中間的一個，像這樣：

for(int start = arr.length/2 - 1; start >= 0; start--) { 
    MaxHeapify(start); 
} 

另外在BuildMaxHeap()你應該改變停止狀態>=和arr.length/2 - 1開始。

希望這會有所幫助。