heap 구현

힙정렬 순서

1. 최대 힙을 만들어준다.

#include <stdio.h>

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

int main(void){
    // 먼저 전체 트리 구조를 최대 힙 구조로 바꿉니다.
    for (int i = 1;i < n;i++){
        int c = i;
        do{
            int root = (c-1)/2;
            if (heap[root] < heap[c]){
                int temp = heap[c];
                heap[c] = heap[root];
                heap[root] = temp;
            }
            c = root;
        }while (c != 0);
    }

    return 0;
}

• 해당과정은 MAX값을 루트 노드로 가져오는 과정이다.
• 전체적인 힙구조를 유지하기 위한 과정이다.
• 해당 코드의 시간 복잡도는 for문 O(n) × O(logn) = O(nlogn)의 시간복잡도가 소요된다.
• 전체 for문에 대해서 do ~ while문을 실행하는데, root는 (c-1)/2 의 식을 가지며, root값을 c에 넣어주어 c값이 0(=전체 루트노드)가 되기전까지 다시 반복적으로 검사한다. 이는, 큰 값을 root쪽으로 정렬시키기 위함이다.

2. 크기를 줄여가면서 반복적으로 힙 구성

// 크기를 줄여가며 반복적으로 힙 구성
    for (int i = n-1; i>=0;i--){
        // 크기가 젤 큰 값을 힙의 맨 뒤로 보냄
        int temp = heap[0];
        heap[0] = heap[i];
        heap[i] = temp;
        int root = 0;
        int c = 1;
        do {
            c = 2 * root + 1;
            // 자식 중에 더 큰 값 찾기
            if (heap[c] < heap[c+1] && c < i - 1){
                c++;
            }
            // 루트보다 지식이 더 크다면 교환
            if (heap[root] < heap[c] && c < i){
                int temp = heap[root];
                heap[root] = heap[c];
                heap[c] = temp;
            }
            root = c;
        } while (c < i);
    }

• 크기가 젤 큰 값을 메모리의 맨 마지막으로 보낸다

  int temp = heap[0];
  heap[0] = heap[i];
  heap[i] = temp;

• 이후 반복적으로 힙정렬을 한다.
• 이번에는 루트부터 차례대로 내려간다.

  int root = 0;
  int c = 1;
  do {
      c = 2 * root + 1;
      // 자식 중에 더 큰 값 찾기
      if (heap[c] < heap[c+1] && c < i - 1){
          c++;
      }
      // 루트보다 지식이 더 크다면 교환
      if (heap[root] < heap[c] && c < i){
          int temp = heap[root];
          heap[root] = heap[c];
          heap[c] = temp;
      }
      root = c;
  } while (c < i);

  • 형제 노드간의 더 큰 노드만 부모노드와 바꿔주면 되기때문에 첫 번째 if문을 활용한다.
  • 이후, 루트노드와 자식노드를 비교해주며 힙을 만들어주면 되기때문에 두번 째 if문을 활용한다.
  • 그렇게 한 번 힙을 만들면, 자식노드의 인덱스를 루트노드의 인덱스로 가져와서 부분트리에 대해서 또 힙을 만들어준다.
  • 단, 해당 힙은 전체 노드의 개수 안에서만 반복한다 while ( c < i )

시간 복잡도

시간 복잡도는 결과적으로 O(nlogn)이 소요된다. N개의 숫자로 힙을 구성할 때, 발생하는 연산도이다. 단순히 이분탐색 트리를 탐색하는데 걸리는 시간은 logn이다. 하지만 이러한 이분탐색트리로 힙을 총 N번 만들기 때문에 이는 O(nlogn)의 시간이 소요되는 것이다.

#include <stdio.h>

int n = 9;
int heap[9] = {2,3,4,5,6,7,8,9,10};

int main(void){
    // 먼저 전체 트리 구조를 최대 힙 구조로 바꿉니다.
    for (int i = 1;i < n;i++){
        int c = i;
        do{
            int root = (c-1)/2;
            if (heap[root] < heap[c]){
                int temp = heap[c];
                heap[c] = heap[root];
                heap[root] = temp;
            }
            c = root;
        }while (c != 0);
    }
    // 크기를 줄여가며 반복적으로 힙 구성
    for (int i = n-1; i>=0;i--){
        // 크기가 젤 큰 값을 힙의 맨 뒤로 보냄
        int temp = heap[0];
        heap[0] = heap[i];
        heap[i] = temp;
        int root = 0;
        int c = 1;
        do {
            c = 2 * root + 1;
            // 자식 중에 더 큰 값 찾기
            if (heap[c] < heap[c+1] && c < i - 1){
                c++;
            }
            // 루트보다 지식이 더 크다면 교환
            if (heap[root] < heap[c] && c < i){
                int temp = heap[root];
                heap[root] = heap[c];
                heap[c] = temp;
            }
            root = c;
        } while (c < i);
    }

    for (int i = 0;i<n;i++){
        printf("%d ", heap[i]);
    }

    return 0;
}