힙정렬(Heap Sort) 알고리즘

해당 블로그의 내용은 학교에서 배운 내용을 개인적으로 정리한 내용이므로, 잘못된 부분이 있을 수도 있습니다. 

 

자료구조 힙(Heap)은 완전 이진 트리의 일종으로, 우선순위 큐를 위하여 만들어진 자료구조이다.

​

여기서 이진 트리란, 하나의 트리에서 모든 부모 노드가 두 개의 자식 노드를 가지고 있는 상태를 말한다. 완전 이진 트리는 이진 트리의 노드가 중간에 비어있지 않고 빽빽이 가득 찬 구조이다.

​

다시 돌아와서, 힙(Heap)은 최솟값이나 최댓값을 빠르게 찾아내기 위한 목적을 가지고 있다. 힙에는 최대 힙과 최소 힙이 존재하는데, 최대 힙은 부모 노드가 자식 노드보다 값이 큰 힙이고, 최소 힙은 그 반대이다.

​

해당 글에서는 부모 노드가 자식 노드보다 큰 최대 힙을 기준으로 작성하겠다.

​

나열된 데이터들을 힙 구조로 재구성하기 위해서는 heapify라는 연산을 실행해야 한다.

​

Heapify 연산

​

heapify는 주어진 하나의 노드를 기준으로 가장 작은 트리 안에서 최대 힙을 만드는 과정이다. 일단 처음 주어진 노드를 루트(부모) 노드로 놓고, 자식들과 비교하여 큰 값을 부모 노드와 교체한다. (부모 노드가 제일 크다면 바꾸지 않고 과정을 중단한다).

​

그리고 처음 주어진 노드가 있는 현재 위치에서 위의 과정을 다시 반복한다. 이렇게 하나 하나씩 최대 힙을 만들어가는 것이다.

​

heapify과정은 한 번만 실행해야 되는 것이 아니라 기본적으로 모든 노드들을 접근하여 heapify과정을 수행해야 하지만, 자식 노드가 없는 노드들은 접근할 필요가 없다.

​

따라서 (0 인덱스 기준으로)

​

2의 (트리의 최대 높이)승 / 2 - 2

​

의 인덱스부터 0 인덱스까지 역순으로 접근하여 heapify과정을 수행하면 된다.

heapify 연산 수행 순서

​

힙 구조를 만들었으니 이제 힙 정렬을 수행할 수 있다. 힙 정렬은 간단하다.

 

나열된 데이터들을 힙 구조로 만들 때는

2의 (트리의 최대 높이)승 / 2 - 2 의 인덱스부터 0 인덱스 까지 역순으로 접근하였지만,

힙 정렬은 그 반대로 하면 된다.

​

​

일단 힙 구조로 구성된 배열에 첫 번째 요소와 마지막 요소를 바꾼다.

​

최대 힙의 첫 번째 요소에는 배열의 최댓값이 들어있으니 이젠 최댓값이 마지막 요소로 들어가게 된다.

 

그리고 배열의 크기를 1 줄인다. (실제로 줄이는 것은 아니고, 변수만)

​

교체한 최댓값은 연산이 완료된 것으로 치고, 더 이상 교체하지 않고 해당 위치에 고정된다.

​

최댓값을 뺀 나머지를 트리의 전체로 간주하고 진행한다.

그리고 이제 첫 번째 요소부터 배열의 마지막 요소까지 순차적으로 heapify연산을 실행한다.

​

그 후, 다시 첫 번째 요소와 마지막 요소를 교체한다. 이 과정을 원래 배열의 크기만큼 반복한다. 이러면 힙 정렬이 완료되게 된다.

​

(힙 정렬 알고리즘의 시간 복잡도는 O(n * logn) 이다)

​

아래는 힙 정렬 알고리즘에 필요한 함수 코드이다. 

​

void heapify(size_t curr){
	if(curr > numItems) return;
    
    size_t left{curr * 2 + 1};
    size_t right{curr * 2 + 1};
    size_t max{curr};
    
    if(left < numItems && items[left] > items[max])
    	max = left;
    if(right < numItems && items[right] > items[max])
    	max = right;
    
    if(max != curr){
    	std::swap(items[curr], items[max]);
        heapify(max);
    }
}

 

 

void buildHeap(){
	for(int i{(int)capacity / 2 - 2}; i >= 0; --i){
    	heapify(i);
}

이 코드에서는 용량(capacity)이 트리의 현재 높이와 같도록 하였기 때문에

반복문의 조건을 위처럼 설정하였다.

void heapSort(){
	size_t orgSize{numItems};
    do{
    	std::swap(items[0], items[numItems - 1]);
        --numItems;
        heapify(0);
    }while(numItems > 0);
    
    numItems = orgSize;
}