7. 힙 정렬(Heap Sort)

#힙이란?

힙은 다음 두가지 성질을 가지는 이진트리이다.

1. 구조적 성질: 완전이진트리

2. 힙의 성질: 최대힙 or 최소힙

*완전이진트리 -마지막 레벨을 제외하고 모든 레벨이 가득 차 있는 상태 -마지막 레벨에서 노드는 왼쪽부터 차례로 채워져야 한다.

*Max Heap & Min Heap -최대힙: 모든 노드 x에 대하여, 그 x의 값은 자신의 자식 노드의 값보다 크거나 같아야 한다. -최소힙: 모든 노드 x에 대하여, 그 x의 값은 자신의 자식 노드의 값보다 작거나 같아야 한다. -최대힙에서 최댓값을 찾는 시간과 최소힙에서 최솟값을 찾는 시간은 O(1)로 상수 시간을 가진다. 그 값은 root에 있기 때문이다. 하지만 최대힙에서 최솟값을 찾거나 최소힙에서 최대값을 찾는 것은 노드를 탐색하는 과정이 필요하므로 트리의 높이 만큼의 시간이 걸린다. O(h) = O(log n)

max heap

*힙에서 n개의 노드가 있을 때,

 - height: log n 내림

 - number of leaves: n/2 올림

 

*힙의 구현

배열로 구현한다.

 

 

#힙 정렬 알고리즘(최대힙 이용)

1. 배열(L)을 최대힙으로 만든다.

 -rebuildHeap을 이용

2. 최대힙을 정렬된 배열로 만든다.

 -힙의 루트에 있는 원소(L[0], 최대 원소)와 마지막 원소(L[last])를 교환한다.

 -힙의 크기를 1 줄이고, 루트가 L[0]인 semiheap에 대하여 rebuildHeap을 이용해 힙으로 만든다.

3. last=0이 될때까지 위의 단계 1-2를 반복한다. 

 

//rebuildHeap이란 root의 left subtree와 right subtree가 heap일 때, root까지 포함하여 heap을 만드는 알고리즘

//rebuildHeap using Max heap
void rebuildHeap(int* a, int root, int n){
    int x = a[root];
    int current = root;
    while(2*current+1 < n){
	int left_child = 2*current+1;
        int right_child = left_child+1;
        int larger_child;
        //left_child와 right_child 중 더 큰 값 찾기
        if(right_child<n && (a[right_child]<a[left_child])) larger_child=left_child;
        else larger_child=right_child;
        //root와 비교해서 heap 만들기
        if(x<larger_child){
	    a[current] = a[larger_child];
            current = larger_child;
        } else break;
    }
    a[current]=x;
}
        
            

void heapsort(int* a, int n){
//step1: 배열 a를 heap(maxheap)으로 만드는 과정
    for(int root=(n-1)/2; root>=0; root--){
        rebuildHeap(a, root, n);
    }
//step2: 최대힙을 정렬된 배열로 만드는 과정
    int heap_size=n;
    for(int last=n-1; last>0; last--){
        int tmp = a[0];
        a[0] = a[last];
        a[last] = tmp;
        heap_size--;
        rebuildHeap(a,0,heap_size);
    }
}

 

 

#수행시간 분석

*step 1의 수행시간

 -rebuildHeap의 수행시간: O(h) //h = log n

 -rebuildHeap (n/2번(내림)) 호출

 => O(n log n)

 그러나 이것은 tight한 분석이 아니다. tight한 분석에 따르면 step1의 수행시간은 O(n)

 

*step 2의 수행시간

 -rebuildHeap의 수행시간: O(log n)

 -rebuildHeap (n-1)번 호출

 => O(n log n)

 

따라서, heapsort의 수행시간은 O(n log n)이다.