자료구조 :: 힙 정렬 Heap sort (c/c++ 구현)

힙 정렬 Heap sort

힙 정렬은 힙 트리를 이용해서 정렬을 하는 방법

 

힙 트리란 트리구조에서 자식노드보다 부모노드가 큰 상태를 뜻한다.

왼쪽 트리를 보면 부모(5)가 자식(2와 3) 보다 크다. 그래서 힙트리이다.

오른쪽 트리는 부모(4)가 자식(6)보다 작다. 그래서 힙트리가 아니다.

 

힙정렬은 위와 같은 힙트리를 만들면서 정렬을 한다.

 

위와 같은 이진 트리가 있다.

현재 이 트리는 힙 트리 상태가 아니다.

 

5와 4, 3 노드를 보자.

4와 5를 바꿔, 힙 트리 상태로 바꿔준다.

 

그 왼쪽 아래 노드 또한

4와 6을 바꿔서 힙 상태로 바꿔준다.

 

다시 5와 6을 바꿔 힙상태로 바꿔준다.

 

 

이렇게 왼쪽은 힙상태가 되었다.

나머지 오른쪽을 힙상태로 바꿔줘야 한다.

 

3과 8을 바꿔 힙상태로 만들어준다.

 

8과 6을 바꿔 힙상태로 바꿔준다.

 

모든 트리가 힙트리 상태가 됐다.

(가장 큰 숫자가 맨 위로 올라오게 된다.)

 

 

root(맨 위에 있는 노드)노드와 맨 마지막 노드와 바꿔준다. (8과 3)

그리고 8 노드를 제외한 나머지 노드에 대해서,

위와 똑같이 힙정렬을 수행한다. (정렬이 될때까지 반복)

 

(코드수정 2018.10.08)

#include <stdio.h>
 
#define parent(x) (x-1)/2
 
void heap(int *data, int num){
    for(int i=1; i<num; i++){
        int child = i;
        while(child > 0){
            int root = parent(child);
            if(data[root] < data[child]){
                int temp = data[root];
                data[root] = data[child];
                data[child] = temp;
            }
            child = root;
        }
    }
}
 
int main(void){
    int num = 9;
    int data[] = {15, 4, 8, 11, 6, 3, 1, 6, 5};
    heap(data, num); // 힙을 만든다. 
    
    for(int i=num-1; i>=0; i--){
        // 가장큰 숫자(root)를 맨 마지막 원소와 스왑 
        int temp = data[i];
        data[i] = data[0];
        data[0] = temp;
        
        // 맨마지막원소(가장큰원소)를 제외하고 다시 힙을 만든다. 
        heap(data, i);    
    }
    
    // 결과 출력 
    for(int i=0; i<num; i++){
        printf("%d ", data[i]);
    }
    
    return 0;
} 
​

 

 

힙정렬의 시간복잡도는 O(N * logN)

N이 무수히 커질경우 N에 비해 logN은 굉장히 작아지므로, O(N)이 된다.

 

정리를 하자면, 퀵정렬, 병합정렬, 힙정렬 모두 시간복잡도는 O(N * logN)을 갖는다.

하지만, 퀵정렬은 최악의 경우 O(N^2)이 될수도 있다.

병합정렬은 추가적인 배열이 필요하므로 메모리공간을 더 사용하게 된다.

힙정렬은 추가적인 배열도 필요하지 않으므로 공간적인 측면에서 효율이며, 항상 O(N * logN)을 보장한다.

 

하지만, 일반적으로 속도를 고려했을때,

퀵정렬의 평균 속도가 빠른편이라 퀵정렬을 많이 사용한다.

 

관련 글

2018/04/28 - [Algorithm] - 자료구조 :: 선택정렬 Selection sort (c/c++ 구현)

2018/04/28 - [Algorithm] - 자료구조 :: 버블정렬 Bubble sort (c/c++ 구현)

2018/04/28 - [Algorithm] - 자료구조 :: 삽입정렬 Insertion sort (c/c++ 구현)

2018/04/28 - [Algorithm] - 자료구조 :: 퀵 정렬 Quick sort (c/c++ 구현)

2018/04/29 - [Algorithm] - 자료구조 :: 병합정렬 Merge sort (c/c++ 구현)

2018/04/30 - [Algorithm] - 자료구조 :: 계수정렬 Counting sort (c/c++ 구현)