힙 정렬 방법에 문제가 있습니다.

Question

자바의 힙 코드에 문제가 있습니다.

나는 지어 졌을 때 주어진 힙을 최대 힙으로 출력하고 싶습니다. 여태까지는 그런대로 잘됐다.

제가 고심하는 부분은 정렬 부분입니다. HeapSort() 메서드는 힙의 가장 큰 요소를 꺼내어 배열의 마지막 위치에 삽입 할 때 정렬 프로세스의 각 단계에서 지정된 배열을 인쇄하고 싶습니다. 몇 가지 이유로 그것은 어떤 점에서 작동하지만 3 회 후에는 정상적인 결과가 아니어야하는 무언가를 던집니다.

저는 건설적인 비판과 도움을 주시면 감사하겠습니다. 미리 코드 스타일을 사과드립니다. 저는 Java에 익숙하지 않았으며 최선을 다했습니다.

Max-Heap: 
[26, 22, 18, 14, 12, 16, 8, 6, 10, 4] 
sorting process: 
[22, 14, 18, 10, 12, 16, 8, 6, 4, 26] 
[18, 14, 16, 10, 12, 4, 8, 6, 22, 26] 
[16, 14, 8, 10, 12, 4, 6, 18, 22, 26] 
[14, 12, 8, 10, 26, 4, 16, 18, 22, 6] 
[12, 26, 8, 10, 6, 14, 16, 18, 22, 4] 
[26, 12, 8, 10, 6, 14, 16, 18, 22, 4] 
[12, 26, 8, 22, 6, 14, 16, 18, 10, 4] 
[26, 22, 12, 18, 6, 14, 16, 8, 10, 4] 
[26, 22, 12, 18, 6, 14, 16, 8, 10, 4] 

그리고 코드 :

public static void max_Heapify(int []a, int i){ 
    int left=2*i+1; 
    int right= 2*i+2; 
    int largest; 
    int heapSize= a.length; 

    if(left<heapSize && a[left]>a[i]){ 
    largest= left; 
    }else{ 
     largest= i; 
    } 
    if(right<heapSize && a[right]>a[largest]){ 
     largest = right; 
    } 
    if(largest != i){ 
     swap(a,i,largest); 
     max_Heapify(a, largest); 
    } 



} 

public static void createMax_Heap(int []a){ 
    int heapSize= a.length; 
    for(int i=heapSize/2; i>=0; i--){ 
     max_Heapify(a, i); 
    } 
    System.out.println("Max-Heap: " +"\n"+Arrays.toString(a)); 
} 

public static void heapSort(int []a){ 
    createMax_Heap(a); 
    System.out.println("sorting process: "); 
    for(int i=a.length-1; i>=1; i--){ 
    swap(a,0,i); 
    int heapSize= a.length-1; 
    max_Heapify(a, 0); 
    System.out.println(Arrays.toString(a)); 
    } 

} 

public static void swap(int[] a, int i, int j) 
{ 
    int tmp; 
    tmp = a[i]; 
    a[i] = a[j]; 
    a[j] = tmp; 
} 
public static void main(String[] args){ 

    int myArr[]={10,4,8,6,26,16,18,22,14,12}; 
    heapSort(myArr); 
} 

Answer 1

당신이 주문하는, 당신은 항상 벡터가 가득 찬 것을 고려하고있다

여기에 출력합니다. 힙을 빌드 한 후에 순서화하는 것은 개념적으로 힙의 모든 최상위 구성원 (힙 정의로 맨 위에 있음)을 제거한 다음 힙을 다시 배치하는 것입니다. 분명히 배열 요소를 제거 할 수 없기 때문에 고려해야 할 마지막 인덱스가있는 변수를 사용하여 "가짜"해야합니다. 기술적 인 측면에서

, 당신의 max_Heapify 기능을 수행해야합니다. 당신이 가장 높은 지수 (따라서 array.length-1에 처음으로 호출되는 참조, 배열과 int lastIndex을 매개 변수로

• 수신
• 시작 루트 (0)와 lastIndex을 스와핑하여 메서드를 호출합니다.
• 그런 다음 힙을 수정합니다 (루트가 자식보다 낮기 때문에 리프가 다시있는 것으로 간주하므로). 재귀 적으로 함수를 호출하십시오. ..

희망이 있습니다.