이번에 알아볼 것은 힙(Heap)이다. 얼핏 힙을 들어보면 어려울 것만 같이 느껴질 수도 있으나
집중해서 보면 이해가 금방되는 구조다.
힙 트리는 간단하게 말하면 이진트리이나 다음과 같은 성질을 가지고 있다.
1. 아래에서 선택
1-1. 부모 ≥ 자식들 (최대 힙)
1-2. 부모 ≤ 자식들 (최소 힙)
2. 완전이진트리
3. 데이터 중복허용
힙은 조밀조밀하게 얽혀있는 완전이진트리이다.
완전이진트리 완전이진트리
완전이진트리에 중간에 이상하게 허한 트리는 아닌 하나씩 촘촘하게 들어가는 트리를 말하니 이 점을 확실히 알아두자.
만약 5 노드 아래의 둘 중 하나 없다면 완전이진트리의 구조가 깨지는 것이다.
힙 트리는 조밀조밀하게 구성되어있다고 했다. 그러기에 힙을 표현하는 방법은 보통 배열을 이용해서 나타낸다.
(정적배열이든 동적배열이든 상관없다.)
중요하게 생각해야하는 가장 기초적인 지식은 트리의 배열 표현 방법이다.
배열로 이진트리를 표현하는 방법은
기본적으로 array 배열의 부모 노드의 인덱스가 i 라 하면,
자식노드는 array[i*2] (왼쪽 자식)와 array[i*2+1] (오른쪽 자식)이 된다.
왼쪽 자식의 인덱스 = (부모 인덱스)*2
오른쪽 자식의 인덱스 = (부모 인덱스)*2+1
힙트리도 이진트리라는 점을 상기하면 금방 이해할 수 있다. 보통 배열로 트리를 표현함에 있어서
자식의 위치에서 부모의 존재를 유추할 때는 반으로 나누면 된다. 그렇기에 루트노드는 1부터 시작한다.
아무리 나눠도 0으로 나눌 수 없으니까 말이다.
힙트리에는 두 가지 종류가 있다.
1-1. 부모 ≥ 자식들 (최대 힙)
1-2. 부모 ≤ 자식들 (최소 힙)
부모의 노드가 자식보다 큰 힙트리와 보모의 노드가 자식보다 작은 힙트리이다.
의도에 맞게 선택하여 프로그래밍 하면 된다.
이제 최대 힙을 이용하여 힙 트리를 설명하겠다.
02: #define MAX 100
03: typedef struct HeapTree04: {
05: int heap[MAX];
06: int size;
07: }HeapTree;
08:
09: HeapTree *Heap;
힙 트리의 구조체이다. 일반적으로 힙트리는 배열이라고 했다. 여기서는 정적배열을 이용한다.
현재 힙트리의 크기를 알 수 있도록 size 라는 변수를 두었다.
힙도 트리다보니 삽입과 삭제의 방법이 중요하다. 일단 삽입에 대해서 이야기해보자.
최대 힙의 경우 새롭게 넣은 값이 부모보다 크다면 값을 교환을 해주면 된다. 하나의 조직에서 서열이 바뀌는 셈이다.
삽입의 방법은
1. 힙 트리의 나머지 공간에 넣는다.
2. 부모와 비교하며 자신보다 작으면 바꾼다.
3. 자신보다 크거나 같은 값이 나올 때까지 2번을 반복한다.
일단 위의 트리에 10을 넣어보자.
그렇다면 새롭게 추가된 10은 부모노드와 비교해가며 자신보다 부모가 클 때까지 서로 위치를 교환하며 주욱 올라간다.
다음과 같이 교환이 모두 끝났다면 제일 위의 노드는 바로 10이 된다.
그렇다면 7을 넣는다면 어떨까? 마찬가지로 차례로 트리의 끝에 추가된다.
그리고 바로 위의 부모노드 5보다 크니 교환을 해서 올라가나 다음 부모인 9보다 작으니 그 상태에서 멈춰버린다.
이것이 바로 힙트리의 삽입과정을 나타낸 것이다.
16: void InserData(HeapTree *Heap, int element)
17: {
18: int i;
19: i=++Heap->size;
20:
21: while( (i!=1) &&
22: (element > Heap->heap[i/2]) )
23: {
24: Heap->heap[i] = Heap->heap[i/2];
25: i/=2;
26: }
27: Heap->heap[i]=element;
28: }
삽입은 뭐 그리 대단한 것은 아니다. 일단 배열의 인덱스를 나타낼 i 를 선언하고
힙의 크기를 +1 시켜준다. (19번줄) 일단 삽입했다고 가정을 하고
끝단에서부터 부모로 올라가라면 2 씩 나눠서 올라가야 한다는 점을 상기시켜보자.
루트의 인덱스는 1이니 루트에 도착하지 않았고 ( i!=1 )
삽입한 요소가 부모보다 클 때 교환이 일어나야 한다. (element > Heap->heap[i/2])
24: Heap->heap[i] = Heap->heap[i/2];
25: i/=2;
24번줄은 부모노드를 자식노드로 끌어내리고 인덱스를 부모노드로 올라가는 것이다.
이렇게 루프가 끝나고 나서 현재의 위치에 요소를 대입하면 힙 트리에서 삽입이 끝난다.
이제 삭제를 알아보자. 힙 트리에서 삭제는 바로 루트를 빼내는 것이다.
루트를 빼내다보니 트리 구조가 무너지게 되는 것은 당연지사. 이를 위해 트리를 재구축 시키는 과정이 필요하다.
재구축 방법은 힙트리의 끝의 단말노드를 루트에 위치시키고 차례로 차식노드들과 비교해가며 재정렬하는 과정이 필요하다.
1. 루트를 꺼낸다.
2. 트리의 끝에 해당하는 단말노드를 임시적으로 루트로 위치시킨다.
3. 루트에 위치한 임시노드는 차례로 자식들과 비교하며 자신의 자리를 찾아간다.
아래의 힙트리에서 삭제연산을 하면 맨 위의 루트 10이 꺼내지게 된다.
꺼내진 자리를 힙 트리의 끝단에 위치한 노드 5가 그 자리를 대신한다.
그리고 임시노드 5는 자신의 위치를 찾아간다. 찾아갈 때 자식의 두 노드 중에서 어디로 나아갈지를 정해야하는데
자식들 중 큰 값이 있는 방향으로 나아간다. 임시노드 5는 자식노드인 9와 4 중, 9로 나아간다. (9>4)
이것을 코드로 표현하면 다음과 같이 된다.
30: int DeleteData(HeapTree *Heap)
31: {
32: int parent=1, child=2;
33: int element, temp;
34:
35: element=Heap->heap[1];
36: temp=Heap->heap[Heap->size--];
37:
38: while( child <= Heap->size )
39: {
40: if( Heap->heap[child] < Heap->heap[child+1] )
41: child++;
42:
43: if( temp >= Heap->heap[child] ) break;
44:
45: Heap->heap[parent]=Heap->heap[child];
46:
47: parent=child;
48: child*=2;
49:
50: }
51: Heap->heap[parent]=temp;
52: return element;
53: }
차근차근 설명해볼까? 삭제를 할 때 꺼내지는 요소(element)는 루트이다. Heap->heap[1]
그리고 임시노드가 되는 것은 힙 트리의 끝에 있는 단말노드이므로 그 자리에서 떼어낸다. Heap->heap[Heap->size--]
35: element=Heap->heap[1];
36: temp=Heap->heap[Heap->size--];
그리고 눈여겨 봐야할 것이 루트에 위치시킨 임시노드(temp)을 자신의 위치로 찾아가도록 하는 과정이다.
32: int parent=1, child=2;
에서 일단 루트에서부터 찾아갈 것이니 parent=1 로, child=2로 선언한다.
38: while( child <= Heap->size )
부모의 위치에서 자식들을 비교해야하기 때문에 힙트리의 크기(Heap->size)를 넘어서면 안 된다.
40: if( Heap->heap[child] < Heap->heap[child+1] )
41: child++;
위에서 임시노드는 자신의 위치를 찾아가기 위해 자식들과 비교하며 나아가는 방향을 정할 때
자식들 중 큰 값을 가지는 자식들로 방향을 정해서 내려간다고 했다.
만약 임시노드가 자식노드보다 크다면, 일단 힙트리의 조건을 만족하기에 교환을 멈춘다. (43번줄)
43: if( temp >= Heap->heap[child] ) break;
그것이 아니면 자식을 부모노드와 교환을 하며(45번줄) 계속 인덱스를 자식단으로 내려간다 (47-48번줄)
45: Heap->heap[parent]=Heap->heap[child];
46:
47: parent=child;
48: child*=2;
루프가 끝났다는 말은 일단 임시노드의 진짜 자리를 찾았다는 의미가 되니 그 자리에 임시노드를 위치시킨다.
51: Heap->heap[parent]=temp;
child 는 일단 *2 를 시킨다고 했으니 parent 가 바로 그 자리인 셈이다.
그리고 처음에 꺼낸 값을 리턴한다. (return element)
여기까지가 힙트리의 삽입과 삭제의 과정이다. 여기서 설명한 힙트리는 최대 힙이다.
최대 힙은 컴퓨터과학 전분야에서 사용되는 우선순위라는 개념이다.
우선순위가 높은 프로세스에게 먼저 메모리를 할당하거나 처리할 때 힙 트리가 사용된다.
이러한 힙트리를 이용해서 힙 정렬도 할 수 있다.
힙 정렬은 그냥 힙트리에 데이터를 막 집어넣고 하나씩 뽑아내면 정렬이 된다!!!!
너무 간단하다! 트리이다보니 시간복잡도는 O(log2 (n)) 이다. 합병정렬(Merge sort)와 최악의 시간복잡도가 같다.
55: void HeapSort(HeapTree *Heap, int *array, int array_length)
56: {
57: int i;
58:
59: for(i=0;i<array_length;i++)
60: InserData(Heap, *(array+i));
61:
62: for(i=0;i<array_length;i++)
63: *(array+i)=DeleteData(Heap);
64: }
힙 정렬 함수는 이렇게 간단하게 구현이 된다. 주욱 넣어서 주욱 빼내면 된다.
이것을 사용하는 메인함수를 만들어볼까?
67: int main()
68: {
69: int i;
70: int array[5]={3,9,1,4,8};
71: HeapTree Heap;
72: InitHeap(&Heap);
73:
74: HeapSort(&Heap,array,5);
75:
76: for(i=0;i<5;i++)
77: printf("%d ",array[i]);
78:
79:
80: return 0;
81: }
오름차순으로 정렬을 하려면 최소 힙으로 고쳐주면 된다. 삽입함수와 삭제함수에서 비교문만 살짝 고치면 된다.
첨부소스를 참조하여 확실히 외워두자.
