힙정렬(Heap Sort), 이진트리 그리고 노드(node)

• 이진트리 : 모든 노드의 자식노드가 2개 이하인 트리구조 (Root / Leaf) 
• 완전 이진 트리
• 최대 힙 : 부모 노드가 자식 노드보다 큰 힙
• 힙 생성 알고리즘
  • 최대 힙이 아닐 때 자식 노드중에서 더 큰값을 부모 노드와 바꿔줌
  • 시간복잡도 : O(N/2 *logN) = O(N) , 힙의 개수를 2의 지수승으로 나누어 주면 높이가 된다(2진트리)
• 힙 정렬의 시간복잡도 : O(N*logN)

#include <stdio.h>

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

int main(void){
    //전체 트리 구조를 최대 힙 구조로 바꿈 
    for(int i = 1 ; 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);
    }
    //크기를 줄여가며 반복적으로 힙 구성
    for(int i = number -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++;
            } 
            //root 보다 자식이 더 크다면 교환 
            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 <number; i++){
        printf("%d ",heap[i]);
    }
}

 

코드 자체를 짜는것보다 2진트리의 구조, 힙 생성 알고리즘의 정의

그리고 힙 정렬에 대해서 이해하는 것이 더 중요한 것 같다.

그림을 그리면서 익숙해지도록 해야겠다.