07-8 힙 정렬

※ 힙 정렬(Heap Sort)

 - 힙 자료구조를 이용해 정렬하는 방법으로 정렬하려는 자료를 힙으로 만든 후 최대 힙이라면 제일 큰 수 부터 뒤에서

   정렬하고 최소 힙이면 가장 작은 수 부터 앞으로 정렬시킨다.

 - 힙정렬은 힙을 만들고 힙에서 원소를 삭제한 후에 최대힙, 최소힙의 조건에 맞게 힙을 재구성 해야한다. 

HeapSort

public class HeapSort {

       

       int[] result =null;

       int resultIdx=0;

       int heapSize = 0;

       int[] maxHeap = null;

       

       public int makeHeap(int a[]){

              int temp;

              int idx;

              

              // 최대 힙 만들기

              if(maxHeap ==null){

                     maxHeap = new int[a.length+1];

                     for(int i = 0; i<a.length; i++){

                           maxHeap[i+1] = a[i];

                           heapSize++;

                     }

                     

                     for(int i= heapSize; i>1; i--){

                           idx = i;

                           while((maxHeap[idx/2] < maxHeap[idx]) && i>1){

                                  temp = maxHeap[idx/2];

                                  maxHeap[idx/2] = maxHeap[idx];

                                  maxHeap[idx]= temp;

                                  idx = idx/2;

                           }

                     }

                     for(int i =1; i<=heapSize; i++){

                           System.out.print(maxHeap[i] + " ");

                     }

              }

              

              int rootValue = maxHeap[1];

              maxHeap[1] = maxHeap[heapSize];

              heapSize --;

              idx = 1;

              

              while(idx*2 <= heapSize || idx*2+1 <= heapSize ){

                    if(maxHeap[idx*2] > maxHeap[idx*2+1]){

                           temp = maxHeap[idx*2];

                           maxHeap[idx*2] = maxHeap[idx];

                           maxHeap[idx] = temp;

                           idx = idx*2;

                    }else if(maxHeap[idx*2] < maxHeap[idx*2+1]){

                           temp = maxHeap[idx*2+1];

                           maxHeap[idx*2+1] = maxHeap[idx];

                           maxHeap[idx] = temp;

                           idx = idx*2+1;

                     }

              }

              printRadixSort();

              

              return rootValue;

       }

       

       public void sorting(int a[]){

              

              if(result ==null){

                     result = new int[a.length];

                     resultIdx = a.length-1;

              }

              

              while(resultIdx>=0){

                     int value = makeHeap(a);

                     result[resultIdx--] = value;

              }

              

              printRadixSort();

       }

       public void printRadixSort(){

              System.out.print("\n정렬된 원소 : ");

              for(int i=0; i <result.length; i++){

                     System.out.print(result[i]+" ");

              }

              System.out.println();

       }

}

Main

public class Main {

       public static void main(String[] args) {

              

              int a[] = {69,10,30,2,16,8,31,22};

              HeapSort hs = new HeapSort();

              System.out.println("\n정렬할 원소 : ");

              for(int i =0; i<a.length; i++){

                     System.out.printf(" %d ", a[i]);

              }

              System.out.println();

              hs.sorting(a);

       }

}