힙 (자료 구조) 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Max-Heap.svg|섬네일| 1부터 100까지의 정수를 저장한 최대 힙의 예시. 모든 부모노드들이 그 자식노드들보다 큰 값을 가진다.]]

'''힙'''({{lang|en|heap}})은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.
* A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.

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

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

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

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

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

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

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

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

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

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

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

 <span style="color:#0000FF;">1 2 3 4 5 6 7 8</span>
 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의 관계를 가지며, 동일한 관계가 모든 노드와 그 자식노드에 대해 성립함을 볼 수 있다.

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

==== 최대 힙 ====
<pre>
algorithm upHeap(Position v):
   while (not isRoot(v)) and key(parent(v))>key(v) do
   {
     swapItems(v,parent(v));
     v<-parent(v);
   }
</pre>

==== 최소 힙 ====
<pre>
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;
   }
</pre>

==== 정 이진 트리를 (최대)힙 트리로 변환 ====
<pre>
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;
    }
  }
</pre>

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

<syntaxhighlight lang="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;
    }
  }
}
</syntaxhighlight>

==== 최대 힙 정렬 ====
최대 힙을 이용한 [[힙 정렬]]을 다음과 같이 구현할 수 있다.
<syntaxhighlight lang="c">
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);
   }
}
</syntaxhighlight>

== 같이 보기 ==
* [[힙 정렬]]

== 각주 ==
<references />

{{자료구조}}

[[분류:힙| ]]