힙 (자료 구조)

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.

• A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.

1부터 100까지의 정수를 저장한 최대 힙의 예시. 모든 부모노드들이 그 자식노드들보다 큰 값을 가진다.

힙에는 두가지 종류가 있으며, 부모노드의 키값이 자식노드의 키 값보다 항상 큰 힙을 '최대 힙', 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙을 '최소 힙'이라고 부른다.

키 값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다.

각 노드의 자식노드의 최대개수는 힙의 종류에 따라 다르지만, 대부분의 경우는 자식노드의 개수가 최대 2개인 이진 힙(binary heap)을 사용한다.

힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징이 있으며, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

이진 힙

이진 힙은 내부노드(internal node)에 키(key)와 요소(element)를 저장한 이진 트리로 다음과 같은 두 가지 특징을 갖는 것을 말한다.

트리를 T, 임의 내부노드를 v 라고 하면 다음과 같다:

1. 뿌리노드를 제외한 각 내부노드는 key(T.parent(v)) < key(v) 또는 key(T.parent(v)) > key(v)이다. (즉, 키 값은 오름차순이거나 내림차순이다.)
2. 마지막 왼쪽 결합 노드들의 레벨을 제외한 다른 모든 레벨들은 완전 이진트리를 형성한다.

힙 리스트(heap list)로 표현할 때 i번째 노드의 왼쪽 자식노드의 위치는 2i가 되며, i번째 노드의 오른쪽 자식노드의 위치는 2i+1이고, 또한 i번째 노드의 부모노드의 위치는 i/2가 된다.

복잡도

힙의 시간복잡성은 $O(\log n)$이다, 왜냐하면 이진트리의 속성$2^{(h-1)}\leq n\leq 2^{h}-1$에서, $\log _{2}(n+1)\leq h\leq (\log _{2}n+1)<{\log _{2}(n+1)+1}$이므로 힙트리의 높이가 $h=\log _{2}(n+1)=O(\log _{2}n)$이 됨을 알 수 있다.

예제

다음의 내용의 배열을 최대힙으로 구성하는 과정을 보여준다. [H|E|A|P|S|O|R|T]

이 배열을 사전 순서에 따라 (즉, A<B<C<…<Y<Z) 힙으로 구성하는 과정은 다음과 같다.

1 2 3 4 5 6 7 8
H E A P S O R T     //중간지점인 p(4번째 인덱스)에서 시작
      ^       ^     //그의 자식은 (왼쪽 자노드 인덱스8)T>P이기 때문에 교환
H E A T S O R P     //A(3번째 인덱스)로 계속되며 A의 왼쪽 자노드는 O(6번째 인덱스)가 되며 오른쪽 자노드는
    ^     ^ ^       //R(7번째 인덱스값)이 되는데 R>O,R>A이므로 R,A교환
H E R T S O A P     //E(인덱스 2)와 그 왼쪽 자노드T(인덱스 4),오른쪽 자노드S(인덱스 5)비교
  ^   ^ ^           //T>S,T>E 결국 T,E교환
H T R E S O A P     //계속 E(인덱스 4)는 왼쪽 자노드P(인덱스 8)과 비교교환하는데 P>E
      ^       ^
H T R P S O A E     //H(인덱스 1)은 그의 왼쪽 자노드T(인덱스 2)와 오른쪽 자노드R(인덱스 3)
^ ^ ^               //T>R,T>H비교 교환한다.
T H R P S O A E     //계속 H를 비교 교환하게 되는데,H(인덱스 2)이므로 왼쪽 자노드P(인덱스 4),오른쪽 자노드
  ^   ^ ^           //S(인덱스5)에서 S>P,S>H비교 교환하게 된다.
T S R P H O A E     //힙 구성 끝.

힙 구성 결과, 뿌리노드인 T는 그 자식노드인 S, R과 비교할 때 T>S, T>R의 관계를 가지며, 동일한 관계가 모든 노드와 그 자식노드에 대해 성립함을 볼 수 있다.

코드

의사 코드

이진 트리를 힙으로 구성하는 과정의 개략적인 의사코드는 아래와 같다.

최대 힙

algorithm upHeap(Position v):
   while (not isRoot(v)) and key(parent(v))>key(v) do
   {
     swapItems(v,parent(v));
     v<-parent(v);
   }

최소 힙

algorithm downHeap(Position v):
   while not (isExternal(leftChild(v)) and isExternal(rightChild(v)) do
   {
   if isExternal(rightChild(v)) then v<-leftChild(v)
   else if key(leftChild(v))<=key(rightChild(v))
      then v<-leftChild(v) else v<-rightChild(v);
   if key(parent(v)) > key(v) then swapItems(v,parent(v))
      else break;
   }

정 이진 트리를 (최대)힙 트리로 변환

makeTreeHeap(H,n) //H full binary Tree, data size n
  for(i <= H/2;i>=1;i <- i-1) do //부모노드 레벨의 역행(4-,3-,2-,1번째)
  {
    p <- i;// 중간지점에서 시작
    for(j<- 2*p;j<=n;j <- 2*j) do //해당 부모노드의 자식노드들에 대한 비교 교환
    {
      if(j<n) then
         if(H[j] < H[j+1]) then j <- j+1
      if(H[p] >= H[j]) exit;
      temp <- H[p];
      H[p] <- H[j];
      H[j] <- temp;
      p <- j;
    }
  }

C 언어

아래의 소스코드는 큰 것이 위로 가도록 하는 최대 힙을 C언어로 구현한 것이다.

void swap(int *a,int *b)
{
  int tmp;
  tmp=*a;
  *a=*b;
  *b=tmp;
}
int max(int a,int b,int c)
{
  int max=0,q;
  if(tree[a]>max) {
    max=tree[a];
    q=a;
  }
  if(tree[b]>max) {
    max=tree[b];
    q=b;
  }
  if(tree[c]>max) {
    max=tree[c];
    q=c;
  }
  return q;
}
void create_heap()
{
  end=N/2;
  for(i=end;i>=1;i--) {
    nnow=i;
    while((qq=max(nnow,nnow*2,nnow*2+1))!=nnow) {
      swap(&tree[nnow],&tree[qq]);
      nnow=qq;
    }
  }
}

최대 힙 정렬

최대 힙을 이용한 힙 정렬을 다음과 같이 구현할 수 있다.

void hsort(int a[],int n) //need to be changed.
{
   int i,temp;
   for(i=n/2-1;i>=0;i--)
      makeTreeHeap(i,n);
   for(i=n-1;i>=1;i--)
   {
      temp=a[i];a[i]=a[0];a[0]=temp;
      makeTreeHeap(1,i-1);
   }
}

같이 보기

• 힙 정렬