이진 힙과 힙정렬 binary heap && heap sort

이 자료는Thomas H. Cormen, Charles E. Leiserson의 introduction to algorithms과
Kenneth H. Rosen 의 Handbook of discrete and combinatorial mathematics의 자료 일부를 번역하고
그 외 여러 wikipedia 자료들을 통합해서 작성된 것입니다.

개인의 이윤을 위해서 작성한 것이 아니며 스스로의 학습용 및 정보 공유 용으로 작성했습니다.

Introduction of Heap sort

이번 포스트에서는, heap sort를 소개하고자 한다. heap sort의 수행복잡도는 O(nlog n)이다.

머지 소트나 퀵소트는 sorts in place가 아니지만,힙 정렬은 삽입정렬과 마찬가지로 sorts in place이다.

merge sort가 무엇인지 까먹었다면 클릭

Insertion sort가 무엇인지 까먹었다면 클릭

sorts in place의 성질은, 즉 크기에 비례하는 별도의 메모리 공간을 쓰지 않고, 상수 메모리 공간을 이용하고 input sequences에서 이렇게 저렇게하면 정렬을 완수할 수 있는 정렬의 그런 성질을 말한다.

즉, 힙 정렬은 메모리 면에서 효율적이라는 것이다. 물론 수행복잡도도, O(n log n)으로 훌륭하다.

그래서 힙 정렬은 Insertion sort나, merge sort의 각각의 장점을 합쳐놓은 것과 같다.

힙 정렬은 단순히 정렬하는 것 외에 또 다른 알고리즘 설계기법이 필요한데, heap 이라고 불리는 자료구조를 이용하는 것이다. 

heap 이라는 자료구조는 지금 우리가 할 정렬인 heap sort만이 아니라, 우선순위 큐라는 자료구조를 효과적으로 만드는데에도 사용된다. 나는 이 포스트의 시작은 힙 정렬에 대해서 하겠지만, 우선순위 큐도 다룰 생각이 있다.

heap이라는 용어가 자료 저장 영역을 뜻하는 데에도 사용한다. 예로 Java 나 Lisp, 또는 JavaScript의 garbage-collected 저장 영역을 표현하는데에 사용되기도 하는데, 여기서의 저장영역으로서의 heap이 뜻하는 것과 heap sort의 heap과는 별 연관이 없음을 밝힌다.  

Heaps

binary heap은 nearly complete binary tree와 같이 볼 수 있는 자료구조이다. 

nearly complete binary tree에 대해 잠깐 용어 설명을 해보자면, 종종 perfect binary tree와 complete binary tree를 섞어쓰므로, (영어로는 perfect, complete 뜻이 비슷하잖아요?!!) 정확한 정의가 헷갈릴 수도 있다. 정확하게는, perfect binary tree는 leaves를 제외한 모든 노드의 자식수는 2이며, 모든 leaves의 깊이가 같은 것을 뜻한다. 

이게바로 perfect binary tree 이다!

nearly complete binary tree는 perfect binary tree로 가는 과정인 binary tree이다. 그래서 leaves를 제외한 모든 node들의 자식수가 2이되, leaves의 깊이가 같지는 않다는 것이다. 다만 그 과정이 왼쪽위에서부터 채워나가는 과정이다.

그러나 저자의 표현방식에 따라 nearly complete binary tree, complete binary tree 또는 left-complete binary tree를 섞어서 쓰므로, 이 포스팅을 통해서 여러분들이 대략 느낌을 알아갔으면 좋겠다. right-complete binary tree는 자료구조나 알고리즘에서 특별히 사용되지 않는다. 따라서, (nearly) complete binary tree는 left-complete binary tree로 알고 있으면 된다.

이제 용어 설명 충분히 한 것 같아요.

아래 트리는 nearly complete binary tree이다. binary heap은 nearly complete binary tree이며, 맨 leaves에서는 왼쪽에서부터 채워나가다 멈춘것 처럼 보인다. 이제 본격적으로 nearly complete binary tree의 구조를 가진 heap에 대해서 이야기해보자.

위의 트리를 살펴보자. 각 노드는 배열의 한 원소와 대응한다. 트리는 가장 낮은 층을 제외하고는 각 층마다 가능한한 최대로 노드를 가지고 있다. 노드는 왼쪽 위부터 채워넣어 진다.

임의의 배열 A로 힙을 표현할 때, 이 배열 A에 대해 두 개의 특성을 눈여겨 볼 수 있다. 배열 A의 크기와 그리고 배열 A의 힙 크기이다. 이때 전자의 크기는, 배열 A에 몇 개의 원소가 있는가, A[1, 2, ... A.length]에 대한 특성이고, 배열 A의 힙 크기는 배열 A에서 힙 구조를 유지하는 원소의 수 A[1, 2, .. A.heap-size]를 뜻하는 것이다. (0 <= A.heap-size <= A.length)

아래의 그림은 위 트리구조를 배열로 표현한 것이다.

트리의 root는 배열 A의 1인덱스라고 하자. A[1] == root of the tree. 그러면 어떤 노드의 인덱스 i가 주어졌을 때 그 노드의 parent node와 왼쪽 child node, 오른쪽 child node의 인덱스는 굉장히 쉽게 구할 수 있다.

int parent (i){
    return i/2;
}

int leftchild(i){
    return i*2;
}

int rightchild(i){
    return i*2+1;
}

위의 구현은 간단하게 bit shift 연산자로도 구현될 수 있다. 자식 노드의 인덱스를 찾는 작업은 "<<"로 가능하며, 부모 노드의 인덱스를 찾는 작업은 ">>"로 간단히 구할수 있다.

max-heap 그리고 min-heap

이진 힙(binary heap)에는 딱 두종류가 있는데 그게 max-heap과 min-heap이다. 두 개 모두는, heap의 모든 노드는 key value를 통해 각각의 min,max-heap 특성을 만족한다.

max-heap에서는 root를 제외한 임의의 노드 i에 대해 다음을 만족한다.

A[ parent(i) ] >= A[ i ]

즉, 임의의 노드 i의 key value는 그 부모의 노드의 key value보다 항상 같거나 작다. 따라서, max-heap에서 가장 큰 key value는 root에 저장되있을 것이다. 그리고 임의의 노드에 root를 두고 있는 부분트리는 그 root 노드가 가지고 있는 key값보다 큰 값을 가지고 있을 수가 없다.

요약하자면 아래 그림과 같다.

min-heap은 그 반대의 경우이다. min-heap은 root 노드를 제외한 모든 노드가 다음의 특성을 만족한다.

A[ parent(i) ] <= A[ i ]

따라서, min-heap에서 가장 key 값이 작은 원소는 root에 있다.

일반적으로 오름차순의 정렬에서는, max-heap을 사용한다. 그리고 key 값이 낮은 순부터 큐에 세우는 우선순위 큐에서는 min-heap이 사용된다. 그러나 일반적인 경우에서야 인것이고, 그 반대인 경우도 굉장히 자주 있을 것이다.

그래서 heap이 뭐야?

간략히 말하면 "heap은 우선순위 트리를 표현한 것을 의미한다.(rosen)" 

heap에는 종류가 많으며, 걔중에 포스팅을 쓰고 있는 내가 이름만 알고있는 것은 binary heap 말고도 다항 힙d-ary heap, 피보나치 힙Fibonacci heap이 있다.

그 중에 우리는 지금 binary heap을 살펴보고 있으며, binary heap은 우선순위 트리이되 nearly complete binary tree의 형태를 띄며, 배열기반array-based로 구현 될 수 있다.

그래서 트리의 특성을 살펴보자면, binary heap은 트리로서의 높이는 log(2)n 이다. (설명이 필요하면 댓글을 부탁드립니다.)

그리고 신기하게도, 힙에서의 수행할 수있는 기본적인 수행은 tree의 특성 중 하나인 높이 log(2) n에 비례하고 따라서 보통 O(log n) 시간복잡도를 가진다. 

그래서 이제 부터는 heap과 관련된 수행들에 대해서 이야기 해볼것이다.

힙의 특성을 유지하기, Heapify

앞에서 설명했듯이 min-heap이건, max-heap이건 각각의 특성이 있다. 

max-heap은 root 노드를 제외한 모든 노드가 A [ parent(i) ] >= A[ i ]를 만족하며, 

min-heap은 root 노드를 제외한 모든 노드가 A [ parent(i) ] <= A[ i ]를 만족하는 특성이 있다.

임의의 배열이 있을때, 이러한 heap 특성을 갖게 해주려면 다음을 수행해주면 된다.

max heap인 경우 임의의 노드 i가 주어졌을 때 이 노드는 자신의 child 노드보다 키 값이 같거나 커야하기 때문에, 임의의 노드 i가 그 규칙을 위배하는지- 즉 그 노드가 자신의 자식들보다 작은지 확인해주고 작다면 i를 트리에서 계속 아래로 가라앉게 만들어, 즉 자신의 자식노드와 자리를 바꾸어 인덱스 i가 max-heap 특성을 계속 유지할 수 있게끔 할 수 있다.

함수의 정의는 다음과 같다.

max-heapify(int i){

   int l = left (i), r = right (i);
   int largest = A [i];

   if ( l < A.size() && A[l] > A[i])      largest = l;
   if ( r < A.size() && A[r] > A[largest])   largest = r;

   if ( largest != i ){
        swap( A[largest], A[i] );
        max-heapify( largest );
   }
}

함수는 현재 노드와 그 자식노드들 A[ i ], A[ left(i) ], A[ right(i) ] 중에서 가장 큰 원소를 찾고 그걸 largest 에 저장한다. 그리고 현재 인덱스i와 largest가 다를 경우 swap ( A[i], A[largest] )를 수행하고, 해당 노드와 바뀐 largest 인덱스를 서브트리 루트로 두듯이, 재귀적으로 max-heapify를 수행한다.

만약, 재귀로 호출된 max-heapify에서 또 max-heap 특성이 위배되었을 때는 또 재귀함수가 수행될 것이다. 

그러나, heapify 함수의 단순한 호출만으로는 모든 트리내의 heap 특성을 만족할 수 없다. 만약에 heapify가 트리 루트에서 시작되었더라도, 트리 루트가 그 자식들보다 key value가 크다고 가정할 수 없다. 예로, 아래의 트리를 생각해보자. 전체적인 트리가 힙 특성을 만족하는가?

heapify 함수는 해당 노드가 자기 자식 노드보다 key value가 낮을 때 까지 떨어지며 떨어지는 도중에는 자기 자신과 자기보다 가장 큰 자식 들과 자리를 바꾼다. 위의 그림(반례)에서 볼 수 있듯이, 한 번의 heapify는 트리 전체를 heap 특성을 유지하게 할 수 없다.

즉, heapify 수행을 통해 해당 노드는 자기 자식 노드 보다 작을 때까지만 트리에서 가라앉고, 그것과 교체되는 큰 노드는 위로 떠오른다. 모습이 거품과 같다. 그래서 나중에 보게될 반복문을 이용한 heapify는 트리 간선을 따라 떠오르고 내려앉는것이 그 모습이 거품정렬과 같다.

단 한번의 heapify는 전체 트리가 heap 특성을 가지게 하지 못한다. 다음만을 만족한다.

그리고 C>=A, D>=A 도 만족한다!

Heapify 한번의 호출과 이런 부등호 명제가 무슨의미고 무슨관계냥?

 -> 부분트리(3노드)에서의 자리를 바꾸는 자기 자식과의 대소관계와
자기 자식 노드끼리의 대소관계를 확실시 시켜준다.

이쯤에서 다시 max- heap의 특성을 요약한걸 보자.

2번 에 동그라미친 저 부분 트리를 보자. 만약 그 부분트리 루트에서 heapify 를 수행하면, 그 부분트리에서 2번 조건을 만족하는 것을 볼 수 있다. 

그렇다 heapify 는 부분트리에서의 heap 특성을 유지 해주기 위해서 사용된다. 그러니 전체 트리를 순회하면서 모든 부분트리를 max-heap 특성을 유지하게 해주면, 전체트리도 또한 max-heap을 유지할 것이다.

우린 이제 반복문을 이용한 전체 트리를 heap 특성을 유지하게 끔 하는 방법을 볼것이다.

Heap 만들기

앞에서 Heapify는 자기 자식노드와 자신, 그리고 자기 자식 노드끼리의 대소 관계를 확실시 시켜준다. 그래서 우리는 전체 트리를 순회하면서 모든 부분트리를 heap 특성을 유지하게끔 해줄것이다.

부분 트리가 있는 곳부터 순회하면 되니, 임의의 배열 A의 크기를 A.size() 라고하고 배열 A의 인덱스가 1부터 시작한다고 할때, 우리는 다음과 같이 해주면된다.

buildheap( A ){

for (int i= A.size()/2; i>=1; i--) heapify(i);

}

A.size()/2 부터 시작하는 것은, 그게 자식노드가 있는 가장 뒤의 노드 인덱스이기 때문이다.
왜 그러냐면, 이 heap은 애초에 left complete binary tree이며, 2^h (여기서 h는 높이) 만큼의 원소들이 있기에, 마지막 한 층을 제외해주는  빼기 2^(마지막층높이) 즉, 나누기 2를 수행하면된다.

이해가 안가면 그려봐도 된다.

기본적으로 Heapify는 재귀이고, 트리의 높이만큼 깊어질수 있으므로 O(log n)의 수행시간을 가진다.
그것을 n/2 만큼 반복하는 buildheap이기에, 전체 트리를 heap 특성을 유지하는데 수행복잡도가 
O( n log n ) 이 걸린다.

응?

아니다! 정확하게는 Build Heap의 시간복잡도는 O ( n ) 이다.

아닙니다. 지금 설명 드리겠습니다.

직관적으로는,

루트에서 수행되는 Heapify는 정확하게 그 높이 log n만큼 내려간다. 그러나, 서브 트리에서부터 차근차근 수행되는 heapify는 확실히 log n보다 작을 것이다. 

맨 아래의 leaf node 들은 ceiling (n/2) 만큼 존재하는데, 이는 자식이 존재하지 않으므로 heapify가 수행되지 않을것이다.

이제 높이가 1인곳을 보면, ceiling (n/2^2) 만큼의 노드가 존재하고, 각 heapify가 1만큼의 수행시간을 가진다.

이제 높이가 i인 곳을 보면, ceiling (n/2^i) 만큼의 노드가 존재하고 각 heapify가 i 만큼의 수행시간을 가진다.

마지막으로 높이가 log(2) n 인 곳을 보면, ceiling (n/2^log(2) n == 1) 만큼의 노드가 존재하고 각 heapify는 log n 만큼의 수행시간을 가진다.

분명한건 Big-O notation에 따라, 약간은 O (n log n) 보다 작을 가능성을 보았다. 

이론적으로 이 finite series를 구하기 위해선, 즉 시간 복잡도를 구하기 위해선 어느정도의 미적분의 개념이 필요하다. 그러나 비록 calculus를 대학에서 수강하였더라도 이를 읽는 분들은 아마 까먹었을 테고, 또는 아직은 이 글을 읽는 여러분이 충분한 개념을 가지고 있다고 믿기 어렵다. 그리고 사실 나도 까먹었기에 다시 살펴봐야 하므로 당장 이론적으로 증명할 수 없지만, 왜 O(n log n)이 아닌 O(n)인지에 대해서 대략적인 느낌을 전달해주고자 한다. 이 부분은 조만간 수정이 될것이다. 

그래서, 이 n을 무한히 늘려보아도 이 Infinite Series는 정확히 n 으로 수렴한다. 따라서 O (n)이 나온다.

본격적으로 힙 정렬하기 Heap sort

힙정렬 어떻게 해야할까? Buildheap을 수행하면 트리의 모든 노드는 해당 heap 특성을 가지게 되며 따라서 루트에는 가장 큰 원소가 있을 것이다. 

따라서, 그 원소를 deheap 하면 된다. 그러면 n개의 원소가 있다고 하면 이 수행을 n번 반복하면된다. 쉽지않은가? 

A를 임의의 수열 sequence이라고 하자.

Heapsort(A){

Buildheap(A);         // for (int i=n/2; i>=1; i--) heapify(A, i);
for i=A.size() to 2
    swap ( A[1], A[i] );
    A.size() -= 1;     //deheap 이다. 맨 마지막으로 보내줌.
    heapify( A, 1);   // heapify는 제외된 노드 를 제외하고 heapify를 수행한다. 

}

Buildheap의 수행복잡도는 O(n) 이고, heapify는 O( log n)이다. 그리고 heapsort 내에선 n번만큼의 heapify가 수행된다. 비록 deheap 과정에서 heap 트리의 높이가 점점 줄어들겠지만, 즉 heapify의 수행복잡도가 약간씩 줄어들겠지만은, 힙 정렬의 수행복잡도는 O (n log n) 이다.

C로 구현한 예제는 다음과 같다. 

https://github.com/ingyeoking13/algorithm/blob/master/tistory/tree/heapsort.c

이로써 binary heap과 heap sort에 대한 포스팅을 마치겠다.

복잡도에 대한 정확한 수학적 증명은 조금 나중으로 미루어 보겠다.