힙 정렬 ( Heap sort )

힙정렬

• 시간복잡도가 O(nlogn)으로 퀵정렬, 병합정렬과 같은 시간복잡도를 가진 정렬 알고리즘
• 병합정렬과는 다르게 추가적인 메모리 필요 X
• 항상 O(nlogn)의 성능을 보여주기 때문에 최악의 경우 O(n^2)의 성능을 보이는
  퀵정렬보다 안정적인 성능을 보인다.
• 이론적으로는 퀵 정렬 병합 정렬보다 우위에 있지만, 단순히 속도만 가지고 본다면 퀵 정렬이
  평균적으로 더 빠르기 때문에 힙 정렬이 많이 사용되지는 않는다.
• 배열을 최대힙 or 최소힙으로 만들어 root에 있는 값을 정렬하는 식으로 구현한다.

---

힙(Heap)

• 완전이진트리 형태의 자료구조
• 힙은 최소힙과 최대힙 두가지로 나뉜다.
• 힙은 일반적인 배열로 표현할 수 있다.

  최대 힙 : "부모 노드 > 자식 노드"를 모든 노드에서 만족하는 완전이진트리 
  최소 힙 : "부모 노드 < 자식 노드"를 모든 노드에서 만족하는 완전이진트리

 

완전이진트리

 - 노드를 삽입할 때 왼쪽부터 차례대로 추가하는 이진트리 ( 모든 노드의 차수가 2 이하로 구성된 트리 )

완전이진트리(각 노드의 왼쪽부터 채워진 이진트리)	그냥 이진트리

 

힙을 일반적인 배열로 표현

 a = {-1,3,4,5,1,7,2,8}; 이라는 배열이 있다고 가정하자.
 a[1]을 루트노드로 잡고 힙트리를 완성하면 밑에 그림과 같다.

 i = 현재 노드의 인덱스

 ☞ 부모노드 = i / 2 (i > 0)

 ☞ 왼쪽 자식 노드     = i * 2

 ☞ 오른쪽 자식 노드  = i * 2 + 1

---

배열을 최대힙(or 최소힙)으로 만들어주는 힙 생성 알고리즘 ( heapify )
  - 힙 구조(최대힙 or 최소힙 구조)로 만들어 주기 위해 하나의 노드에 대해서 수행하는 알고리즘
  - 특정 노드의 두 자식 중에 더 큰 자식 <-> 자기 자신 스위칭
     ( 이 과정을 모든 노드에 대해서 반복 )

5 때문에 최대 힙 구조 X	heapify() 후 최대 힙 구조 O

  - 하나의 노드에 대해 한 번 heapify()를 수행하는데 걸리는 시간 : O(logN)
 
  - 전체 노드가 힙 구조를 다 만족하도록 만드는데 걸리는 시간 ( 제일 왼쪽 아래 노드부터 heapify() 시작 )
     ( == 트리에 있는 모든 노드에 대해 heapify()를 수행하는데 걸리는 시간 )
     => O(N * logN) ( 노드 개수 * 특정 노드에 대해 heapify() 1번 할 때 걸리는 시간 )

 

  - 실제로 전체를 힙 구조를 만족하도록 만드는데 걸리는 시간
        Ex)  이진탐색트리의 높이 : logN / 총 노드 갯수 : N
             - 실제로는 노드 갯수의 반만큼만 heapifiy()를 하면 되므로 ( 리프 노드들은 자식이 없기 때문에 할 필요 x )
                => N/2 * logN 이 된다.
                => N이 무한히 커진다면 N/2  >  logN라서 logN은 상수급으로 작아진다.
                => 그러므로 시간복잡도가 O(N * logN)이긴 하지만 logN이 상수급으로 작아지기 때문에 거의 O(N)에
                     가까운 속도를 낼 수 있다.

---

힙정렬의 원리

- 힙을 이용해 정렬을 하기 위해서는 이 힙을 최소힙이나 최대힙으로 만들어야 한다.
  힙이 최소힙 or 최대힙이 되었을 때 root는 항상 힙에서 최대값 or 최소값이 나오게 되어 있다.
  이 때 root를 힙의 마지막 노드와 교체한 뒤 힙의 마지막을 제외한 후 다시 최소힙이나 최대힙을
  만들어 준 후 root를 마지막 노드와 교체하는 방식으로 계속 반복한다. 

  힙 정렬 순서
  1) 정렬되지 않은 배열 생성

  2) 제일 처음에 이 배열을 최소힙 or 최대힙으로 구성 ( 모든 노드에 대해 힙 생성 알고리즘 heapify() 사용 )
  3) root <-> 마지막 노드 교체
  4) 마지막 노드를 제외한 상태로 다시 최소힙 or 최대힙 구성 ( root노드에 대해 다운힙 : O(logN) )
  5) 3 ~ 4번 반복

  => 최종적으로 힙정렬하는데 드는 시간
       => 처음 최대힙으로 만드는데 걸린 시간 + 스위칭한 후 root에 대해 다운힙하는데 걸리는 시간
            => O(N)  +  O(N * logN)
                 => O(N * logN)

---

힙 정렬 구현 코드

#include<stdio.h>
#include<iostream>

using namespace std;

int n = 7;
int heap[8] = {-100,1,9,5,4,7,2,8}; 

void heapify(int i){
  int parent = i;
  int child = i * 2;

  if(heap[child] < heap[child+1]) child++;

  if(heap[parent] < heap[child]){
    swap(heap[parent],heap[child]);
    if(child <= n / 2){
      heapify(child);
    }
  }
}

void heapSort(int i){
  int root = 1;
  int child = 2;
  swap(heap[root], heap[i]);

  //마지막 노드를 제외하고 최대힙으로 구성
  do{
    child = root * 2;
    if((heap[child] < heap[child + 1]) && (child < i - 1)){
      child++;
    } 

    if(heap[root] < heap[child] && child < i){
      swap(heap[root],heap[child]);
    }

    root = child;
  }while(child < i);
}

int main(){

  //처음에 최대 힙으로 만들기
  for(int i = n / 2; i >= 1; i--){
    heapify(i);
  }

  //힙 정렬 수행
  for(int i = n; i > 0; i--){
    heapSort(i);
    // printf("%d : ",i);
    // for(int j = 1; j <= n; j++){
    //   printf("%d ",heap[j]);
    // }
    // printf("\n");
  }


}