힙 정렬(heap sort)

개념

- 힙 구조를 만들어서 정렬하는 알고리즘

- 루트 노드는 항상 최댓값 혹은 최솟값을 가지며 정렬 수행 시 힙 구조 재형성필요

- 루트 노드의 값을 가장 마지막 노드의 값과 교환 + 힙 트리의 크기를 감소시키면서 정렬 수행

static final int NUMBER = 9;
static int[] heap = { 7,6,5,8,3,5,9,1,6 };

static void heapSort(int[] arr) {
  // 1. 전체 트리 구조를 최대 힙 구조로 변경 
  for (int i = 0; i < NUMBER; i++) {
    int c = i;
    do {
      //특정 원소의 부모노드를 가리킴
      int root = (c-1)/2; 

      //부모의 값보다 자식의 값이 더 큰 경우, 값 변경(최대 힙 구조 형성)
      if(heap[root] < heap[c]) {
        int temp = heap[root];
        heap[root] = heap[c];
        heap[c] = temp;
      }
      //값을 바꿔준 후에는 변경된 부모 노드를 기준으로 다시 상위 노드와 비교하여 힙 구조인지 체크 
      c = root;
      } while(c != 0);
   }

    // 2. 크기를 줄여가며 반복적으로 힙을 구성하여 정렬 수행
    for (int i = NUMBER-1; i >= 0; i--) {
      //2-1 최대 힙을 마지막 노드와 값 변경(가장 큰 값을 맨 뒤로 보내는 작업)
      int temp = heap[i];
      heap[i] = heap[0];
      heap[0] = temp;

      //2-2 값 교환 후, 힙 구조 형성
      int root = 0;
      int c = 1;
      do {
      	c = 2 * root + 1; //c는 루트의 자식
      
        //자식 중에 더 큰 값 찾기 
        //조건(c < i-1)은 이미 정렬된 노드는 힙구조 형성에 사용하지 않도록 하기 위해서 필요
        if(c < i-1 && heap[c] < heap[c+1]) {
          c++;
        }
        
        //루트보다 자식이 더 크다면 교환
        //조건(c < i)은 이미 정렬된 노드는 힙 구조를 형성에서 제외하기 위해서 필요
        if(c < i && heap[root] < heap[c]) {
          int temp2 = heap[root];
          heap[root] = heap[c];
          heap[c] = temp;
        }
        root = c;
    } while (c < i);
  }
}

 

※ 힙 생성 알고리즘(logN) x 전체 원소의 수(N)

※ 전체 시간복잡도 O(N*log N)