내가 이해하려고 쓰는 [힙정렬] Heap sort

* 유투버 동빈나님의 영상을 참조하여 정리한 것입니다.

 

 

 

힙정렬(Heap sort)은

기본적으로 힙트리 구조(Heap tree structure)를 이용하는 정렬방법이므로

주어진 데이터가 힙트리 구조를 가지도록 만들어야 한다.

 

 

 

이진트리(Binary tree)는

주어진 데이터를 각 노드(Node)에 담았을 때, 모든 노드의 자식노드가 2개 이하인 트리구조이다.

최상단 노드를 루트노드(Root node)라고 부르며, 최하단 노드를 리프노드(Leaf node)라고 부른다.

 

그 중 완전이진트리(Complete Binary tree)는

데이터가 루트 노트부터 시작해서 그 아래 왼쪽 자식노드, 오른쪽 자식노드... 순서로 들어가는 구조이다.

즉, 이진트리의 노드가 중간에 비지않고 빽빽히 가득차 있는 구조를 말한다.

 

 

 

힙(Heap)은

위의 이진트리를 통해 최솟값 또는 최댓값을 빠르게 찾아내서 정렬을 수행할 때 쓰인다.

트리내의 모든 부모노드가 자식노드보다 큰 상태를 만족하는 힙, 최대힙(Max Heap)이어야 힙정렬을 수행할 수 있다.

하지만 특정 부분에서 최대힙을 만족하지 않는 경우가 있을 수 있다.

이 경우에는 자식 중 부모보다 큰 값을 부모와 바꿔준다.

이를 힙생성 알고리즘(Heapify Algorithm)이라고 한다.

 

이렇게 자식과 부모의 값을 바꿔준 후에 아래의 자식과의 최대힙 상태가 붕괴된다면

또 다시 그 아래의 자식 중에서 부모보다 더 큰 자식과 부모를 바꿔준다.

자식이 더 이상 존재하지 않을때까지 계속 반복한다.

 

 

 

힙생성 알고리즘을 한 번 수행할 때의 시간복잡도는 트리의 높이인

(계속 이분할 되는 알고리즘의 시간복잡도는 항상 밑이 2인 로그를 따른다)

예를 들어서, 데이터의 갯수가 1024개라면,

트리의 첫째줄 1개 + 트리의 둘째줄 2개 + 트리의 셋째줄 4개 + 트리의 넷째줄 8개... = 1024가 되는 트리는 약 10줄 정도이다.

 

모든 노드에 Heapify Algorithm을 수행하게 되면 데이터갯수인 n이 곱해져서

이 힙정렬의 시간복잡도가 된다.

 

 

 

힙정렬을 하는 순서는

1. 주어진 데이터를 완전이진트리에 삽입되는 순서대로 Index를 붙여서 배열에 담아준다.

2. 위에서부터 부모와 자식 한세트씩 보면서 크기를 비교한 후 필요시마다 Heapify Algorithm을 수행한다.(하향식)

3. 최대힙이 완성되고 나면 제일 큰 값이 무조건 Root에 있다. 이 값과 가장 마지막 값을 바꿔준다.

4. 그럼 가장 마지막 인덱스에 제일 큰 값이 들어가서 그 값은 정렬이 이루어지므로 이 마지막 인덱스는 더 이상 보지 않는다.

5. 2~4를 반복한다. 전부 정렬이 될 때까지.

 

 

 

코드를 구현해보면 다음과 같다.

#include <stdio.h>

int heap[7] = { 1,4,7,5,3,8,2 };
int number = 7;

int main(){
    int temp, i;
    while (number != 0){
        for (i = 1; i < number; i++){ 인덱스0은 항상 Root node이므로 1부터 시작해서
            int c = i;                차례대로 자식노드(children node=c)에 넣어준다.
            while (c != 0){
                int root = (c - 1) / 2; 아래 설명
                if (heap[c] > heap[root]){
                    temp = heap[c];
                    heap[c] = heap[root];
                    heap[root] = temp;
                } 
            c = root; 
            } 
        }
    여기까지가 Heapify algorithm을 수행하여 최대힙구조를 만든 것이다.
    
    이 최대힙을 만족하는 상태에서 root를 맨 뒤로 보낸다.
        temp = heap[0];
        heap[0] = heap[number - 1];
        heap[number - 1] = temp;
        number--; 
    }
    
    for (i = 0; i < 7; i++){
        printf("%d", heap[i]);
    }
    
return 0;
}

힙정렬을 하는 순서에 맞춰서 하나씩 차근히 살펴보자.

1. 일단 이진트리 형태로 만들어주면 다음과 같이 생겼다. 그리고 index를 차례대로 빨간 숫자로 붙여주었다.

* 트리를 보았을 때 자식이 4와 7인 경우의 부모는 1이다. 인덱스로 보면, 자식이 1과 2인 경우 부모는 0인 것이다.

또한 자식이 5와 3인 경우의 부모는 4인데, 이를 인덱스로 보면 자식이 3과 4인 경우의 부모는 1인 것이다.

즉, 자식과 부모의 인덱스 관계는 자식 인덱스에서 1을 빼고 2로 나누었을 때의 정수값만 도출되면 된다.

그래서 root = (c-1)/2라는 계산식이 나온다. 

 

 

 

부모와 자식을 바꿔야 된다는 내용은 알아도, 나는 인덱스와 루프를 엄청나게 헷갈려하기 때문에

이해가 아무 쓰잘데기가 없다. 코드로 구현을 정말 못한다. 그래서 하나씩 전부 적어보겠다.

 

2. 위에서부터 쭉 보면서 Heapify Algorithm을 수행한다.

i=1에서 시작한다. c=1, root=(1-1)/2=0이므로

heap[root]=heap[0]=1과 heap[c]=heap[1]=4을 비교해보면 자식노드가 더 크다. 따라서 자식과 부모를 교체해준다.

그럼 차례대로 {4,1,7,5,3,8,2}가 된다. 그리고 c에 root=0를 넣으면 c=0이 되므로 while(c!=0)이 종료된다.

i=2이 된다. c=2, root=(2-1)/2=0이므로

heap[root]=heap[0]=4와 heap[c]=heap[2]=7을 비교해보면 자식노드가 더 크다. 따라서 자식과 부모를 교체해준다.

그럼 차례대로 {7,1,4,5,3,8,2}가 된다.  그리고 c에 root=0를 넣으면 c=0이 되므로 while(c!=0)이 종료된다.

i=3이 된다. c=3, root=(3-1)/2=1이므로

heap[root]=heap[1]=1과 heap[c]=heap[3]=5를 비교해보면 자식노드가 더 크다. 따라서 자식과 부모를 교체해준다.

그럼 차례대로 {7,5,4,1,3,8,2}가 된다. 그리고 c에 root=1을 넣으면 c=1이 되고 while(c!=0)이 계속 수행된다.

아래 노드에서 교체가 발생하면 상위 노드의 최대힙을 깨뜨릴 수 있어서 상위 노드까지 다 봐주어야 한다.

따라서 c가 0인덱스가 될때까지 계속 수행해 주어야 하는 것이다.

c=1, root=(1-1)/2=0이므로 비교했을 때 부모노드가 더 크다. 따라서 if문이 수행되지 않는다. c에 root=0을 넣어 while도 종료된다.

i=4가 된다. c=4, root=1이고 비교시 부모가 더 크므로 if문이 수행되지 않고, c=1이 되므로 while은 계속 수행.

c=1, root=0 여전히 상위노드도 최대힙을 만족하므로 if문이 수행되지 않는다. c=0이므로 while 종료.

i=5가 된다. c=5, root=2이고 비교시 자식이 더 크므로 교체된다. {7,5,4,1,3,8,2}가 되며 c=2이므로 while 계속 수행.

c=2, root=0이고 자식이 더 크므로 교체한다. {8,5,7,1,3,4,2}가 되고 c=0이 되어 while 종료.i=6이 된다. c=6, root=2이고 비교시 부모가 더 크므로 if문이 수행되지 않는다. c=6이므로 while은 계속 수행.c=2, root=0이고 부모가 더 크므로 if문이 수행되지 않는다. c=0이므로 while 종료.i=7이 되면 for문에서 인덱스를 초과하여 빠져나간다.

 

그림으로 백날 그려봤자 글로 안쓰면 이해가 안가서 그냥 글로 적었다.pythontutor.com/visualize.html#mode=edit여기에서 코드 복붙해서 차례로 visualize해보면 명확하게 알 수 있다.

 

3. 제일 큰 값을 이제 뒤로 보낸다.

이제 root값과 맨 마지막값을 바꿔준다. {2,5,7,1,3,4,8}이 되며 가장 마지막값에 가장 큰 값이 들어와서 8은 정렬이 완료된다.

 

4. 뒤로 보내서 정렬이 완료된 값은 더 이상 보지 않는다.

그래서 number--; 코드가 필요한 것이다.

 

5. 전부 정렬이 될 때까지 2~4를 반복해야 한다.

number를 계속 -1해서 결국 number=0이 되면 더 이상 수행할 것이 없으므로while(number!=0) 조건으로 2~4를 반복하게 만들어준다.