DataStructure] 힙(Heap, 히프) 만들기 - 1

 

힙(혹은 히프)은 최솟값(또는 최댓값)을 빠른 시간에 접근하게 만들어진 자료구조로, 최댓값을 접근하려면 최대힙을, 최솟값을 접근하려면 최소힙을 사용한다. 두 힙은 대칭적인 관계를 갖고 있기 때문에, 하나를 이해하면 다른 힙은 쉽게 이해할 수 있다.

 

힙에 대해 정확히 모르는 사람들을 위해서 이해를 돕기 위한 그림과 힙의 조건에 대해서 이야기를 잠깐 하겠다.

 

힙은 위 그림처럼, 각 노드의 값이 자식 노드들의 값보다 크거나 작은(클 경우 최대힙, 작을 경우 최소힙) 완전이진트리를 뜻한다. 거의 대부분이 정렬 파트를 다루면서 힙 정렬을 통해 이 구조에 대해서 아는 경우가 대부분이다.

 

오늘은 힙이 어떤 식으로 생겼는지 보는 것보다는, 힙 자료구조를 구성하는데 요구되는 시간복잡도가 O(n)인 것에 대해서 이야기를 해볼까 한다.

 

처음 힙 구조를 접하고 힙을 구성할 때에는 O(nlogn)의 시간 복잡도를 갖는 알고리즘, 힙에 자료를 하나씩 추가하는 방법으로 구조를 만드는 것이 대부분이다.

나 또한 힙을 다룰 때 항상 그런 식으로 접근을 했고, 데이터 자체가 수 억 개의 데이터를 다루거나 환경이 제한적이지 않아서 문제될 일이 없었다. 하지만, 자료구조와 알고리즘에 대해서 배운 이 시점, 좀 더 효율적인 방법으로 힙을 구성할 수 있다는 사실을 알게 되었다.

 

소개하고자 하는 알고리즘은 bottom-up 방식의 알고리즘으로 힙의 특성, 자식노드들은 반드시 자신보다 크거나 작아야 한다는 점을 바탕으로 구성해나가는 알고리즘이다.

 

 

BuildHeap(A)

{

    for(i=1;i<=n/2;i++)

    DownHeap(i)
}

 

DownHeap(i)

{

    leftChild=2i;

    rightChild=2i+1;

    if(leftChild<=n && A[leftChild]>A[i])

        bigger=leftChild

    else

        bigger=i

    if(righChild<=n && A[rightChild]>A[i])

        bigger=rightChild

    if(bigger!=i) {

        SWAP(A[i],A[bigger])

        DownHeap(bigger)

    }
}

 

자식 노드 둘 중 하나 큰 것을 bigger라고 해두고, 힙의 크기를 바탕으로 힙에 포함되는지 분류를 실시하는 과정을 반복한다. 이 작업을 계속 반복하면서 시작노드(i)가 bigger와 같다면 힙 조건을 만족하는 것으로 간주해 더 이상 자리바꿈과 DownHeap 호출이 진행되지 않는다.

다음 포스트에서는 위 알고리즘이 어떤 식으로 작동하는지 시각적으로 보고, 시간 복잡도가 O(n)임을 검증해보도록 하자.