잘못된 출력을 제공하는 어레이에서 다운 힐

Question

힙 정렬을 실행하는 프로그램을 작성 중입니다. removeMin 함수를 실행하려고 할 때, 항상 잘못된 결과를 얻고있는 것처럼 보입니다.

의 순서로 I 입력 (10) 정수 예를 들어 :

3, 6, 8, 3, 89, 35, 7, 9, 1, 4 

내가

1, 3, 3, 4, 6, 7, 8, 9, 35, 89 

을 기대하지만 얻을 :

: 여기

1, 3, 3, 4, 6, 7, 8, 9, 35, 35 

내 코드 힙 코드

public class heapsort { 

private Integer[] myHeap; 
private int size; 
private int maxSize; 

public heapsort (int x){ 
    myHeap = new Integer[x+1]; 
    maxSize=x; 
    size=0; 
} 

public void min(){ 
    if (isEmpty()) 
     System.out.print("Is empty"); 
    else 
     System.out.println(myHeap[0]); 
} 

public boolean isEmpty(){ 
    return (size==0); 
} 

public int size(){ 
    return size; 
} 

public void insert(int x){ 
    if (size==maxSize) 
     System.out.println("Heap is full"); 
    else{ 
     size++; 
     myHeap[size] = x; 
     upheap(size); 
    } 
} 

public void upheap(int x){ 
    int temp; 
    if (x>1){ 
     if (myHeap[x]<myHeap[x/2]){ 
      temp = myHeap[x]; 
      myHeap[x]=myHeap[x/2]; 
      myHeap[x/2]=temp; 
      upheap(x/2); 
     } 
    } 
} 

public void removeMin(){ 
    int temp; 
    temp = myHeap[1]; 
    myHeap[1]=myHeap[size-1]; 
    size--; 
    if (size>1){ 
     downheap(1); 
    } 
    System.out.println(temp); 
} 

public void downheap(int x){ 
    int temp; 

    int temp, minIndex, left=2*x, right=2*x+1; 

    if (right>=size){ 
     if (left>=size) 
      return; 
     else 
      minIndex=left; 
    } 

    else{ 
     if (myHeap[left] <= myHeap[right]) 
      minIndex = left; 
     else 
      minIndex = right; 
    } 

    if (myHeap[x] > myHeap[minIndex]){ 
     temp = myHeap[minIndex]; 
     myHeap[minIndex]=myHeap[x]; 
     myHeap[x]=temp; 
     downheap(minIndex); 
    } 
} 

,

내 메인 프로그램 얹는 :

public static void main (String[] args){ 
    int i=0; 
    Scanner input = new Scanner(System.in); 
    System.out.println("Enter array size: "); 
    int n = input.nextInt(); 

    heapsort myArray = new heapsort(n); 
     System.out.println("Please input integers"); 
    for (i=1; i<=n; i++){ 
     myArray.insert(input.nextInt()); 
    } 

    while (!myArray.isEmpty()){ 
     myArray.removeMin(); 
    } 
} 
} 

Answer 1

그것은 당신의 종류가 진행 한 요소를 떨어 뜨리는 몇 가지 실행에서 날 것으로 보인다 다음 회 마지막 요소를 인쇄합니다. 나는 두 숫자 3과 4의 배열의 크기를 입력 (4, 3), I는

3 
3 

을 얻는 경우에 나는 이것이 당신이 removeMin에서 일어나는 일에 대해 생각 할 수 있어야 간단한 충분한 경우라고 생각합니다 방법. 배열은 [null, 3, 4] (0 번째 요소를 사용하지 않으므로)이며 크기는 2입니다. temp은 무엇입니까? 어떤 배열 요소를 myHeap[1]에 복사하고 있습니까? 새로운 size은 무엇입니까? downheap(1)을 호출 할 수 있습니까? 인덱스는 0부터 시작한다는 것을 기억하십시오. 고의적으로 답변을 남겨두고 있습니다. 귀하가 알아서 버그를 수정할 수 있다고 믿습니다.

추신 : 저는 버그라고 생각하는 것을 수정했습니다. 이제 3의 배열 크기와 1 2 3을 입력하면 얻을 수 있습니다.

1 
3 
2 

그래서 내가 틀렸거나 하나 이상의 버그가 있습니다. 희망을 찾을 수있을 것입니다. 디버깅 기술을 훈련하는 것이 좋습니다. 마지막으로 필요한 것은 아닙니다.

PPS min 방법이 잘못되었으므로 사용하지 않으셔도됩니다. 그리고 당신은 을 downheap()에 두 번 선언하고 있습니다 (아마 컴파일되지 않았을 것입니다).

편집 : 경고 : 스포일러

스티븐 O'C, 나는 당신이 지금 당신의 버그를 발견, 그래서 당신이 알고있는 것을 확인하여 학습에 어떤 해를, 그리고 다른 사람이하지 않는 생각 함께 읽는 것도 알고있는 것에 관심이있을 것입니다. 그래서 내가 발견 한 버그와 그 버그를 수정하는 방법이 있습니다.

첫 번째 오류는 removeMin() 방법입니다.

myHeap[1] = myHeap[size - 1]; 

이 줄은 우리가 정상에 힙의 마지막 요소를 이동하려는

myHeap[1] = myHeap[size]; 

해야한다.요소는 인덱스 1 ~ size에 있기 때문에 size에서 1을 빼면 안됩니다 (배열을 0부터 사용 했으므로 size - 1은 정확했을 것입니다.)이 오류로 인해 힙에서 마지막으로 끝나는 요소가 누락되었습니다 . 큰 요소로이 수정

코드는 정렬 된 출력의 두 가지 요소가 제대로 작동하는 것처럼,하지만 지금하고 교환 할 수 버그가 downheap()이 두 줄에 있습니다.

if (right >= size) { 
     if (left >= size) 
      return; 

right 또는 left이 각각 size과 같으면 여전히 요소를 가리 킵니다. 힙 (heap). 그래서이 경우 우리는 체질 작업을 할 필요가 있으며,이 시점에서 돌아올 수 없다. 첫 번째 오류와 매우 유사한 오류입니다. 이 문제를 해결하기 위해보다 엄격한 연산자를 사용합니다.

if (right > size) { 
     if (left > size) 

이 수정 프로그램으로 더 이상 버그를 발견하지 못했습니다.