힙 정렬(Heap sort)

: 자료구조 힙(최대 힙, 최소 힙)을 이용한 정렬 방법

• 최대 힙, 최소 힙으로 내림차순, 오름차순 정렬을 할 수 있다.
• O(n log n) 의 시간복잡도를 가져, 가장 빠른 정렬 방법 중 하나이다.
  • 비교할 때 자식, 부모 노드로 이동 log N * 모든 노드 N개에 대해 수행 N
• 힙은 완전 이진 트리 구조를 가진다.
• 힙의 특성상 가장 앞의 값이 항상 많이 쓰인다.
  • 따라서, 가장 유용할 때는 가장 큰 몇개만 필요할 때

힙의 삽입

과정

1. 힙에 새로운 요소가 들어오면, 힙의 leaf노드에 삽입한다.
2. 새 노드가 우선순위 규칙에 맞는지 확인한다. 부모 노드와 자리를 교체한다.
3. 2번의 과정을 통해 우선순위가 맞게 되면 끝. 더이상 교환하지 않는다.

코드

// 배열로 구현.
void insertMaxHeap(int heap[], int target) {
  int i = sizeof(heap) - 1;
  heap[i] = target;
  
  while(heap[i] > heap[i / 2]) {
    int tmp = heap[i];
    heap[i] = heap[i / 2];
    heap[i / 2] = tmp;
  }
}

힙의 삭제

과정

1. 항상 Root노드가 삭제.(최대 힙은 최대 값, 최소 힙은 최소 값)
2. 삭제된 Root노드에 Leaf 노드를 가져온다.
3. Root가 된 Leaf값을 자식과 비교해, 자식 중 우선순위에 더 가까운 것과 swap
   • 물론, 모든 노드의 순서가 우선순위를 만족하지 않게 될 수도 있음. 그런데, 문제가 되지 않는 이유는 항상 맨 앞의 값 으로만 접근하기 때문
     • 모든 노드에 알고리즘을 사용하지는 않아도 되기 때문에 O(N)의 성능을 내기도 한다고 함.

코드

// root가 1이라고 가정
void deleteMaxHeap(int heap[]) {
  heap[1] = heap[sizeof(heap) - 1];
  heap[sizeof(heap) - 1] = 0;
  int lChild = 2, rChild = 3;
 	int me = 1;
  
  int size = sizeof(heap);
    
  while(lChild < size && rChild < size) {
    if(heap[lChild] > heap[me]) { // 왼쪽 자식
      swap(heap, lChild, me);
      me = lChild;
    }
    else if(heap[rChild] > heap[me]) { // 오른쪽 자식
      swap(heap, rChild, me);
      me = rChild;
    }
    else
      break;
    
    lChild = me * 2;
    rChild = me * 2 + 1;
  }
}

Reference)

https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html