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; 

자바 배열이 루트에 대한 있도록 기반 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에서 시작합니다.

희망이 도움이됩니다.