[include(틀:이론 컴퓨터 과학)]
[목차]
== 개요 ==
Heap tree
여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 [[트리(그래프)#s-4.1|이진 트리]]. 짧게 힙(Heap)이라고 줄여서 부르기도 한다.

== 정의 ==
[[파일:4-15-1.png|width=400]] 
영단어 힙(heap)은 '무엇인가를 차곡차곡 쌓아올린 더미'라는 뜻을 지니고 있다. 힙은 항상 [[트리(그래프)#s-4.1|완전 이진 트리]][* 트리의 위부터 아래, 왼쪽부터 오른쪽의 순서로 빠짐없이 가득 차있는 이진 트리]의 형태를 띠어야 하고, 부모의 값은 항상 자식(들)의 값보다 크거나(Max heap 최대 힙), 작아야(Min heap 최소 힙)하는 규칙이 있다. (그러므로 사진은 최소 힙(Min heap이다.) 따라서 루트노드에는 항상 데이터들 중 가장 큰 값(혹은 가장 작은 값)이 저장되어 있기 때문에, 최댓값(혹은 최솟값)을 <math>O(1)</math>안에 찾을 수 있다.

단순히 최댓값(최솟값)을 <math>O(1)</math>안에 찾기 위해서라면 "항상 [[트리(그래프)#s-4.1|완전 이진 트리]]의 형태여야 한다"는 조건을 만족시킬 필요는 없다. [* 극단적으로 말해서, 최댓값/최솟값을 항상 헤드에 두고, 나머지 데이터는 비교하든 말든 그냥 뒤에 쭉 이어붙인 [[연결 리스트]]로도 최댓값/최솟값을 상수 시간 내에 찾을 수 있다.] 완전 이진 트리를 사용하는 이유는 삽입/삭제의 속도 때문이다. 물론 '힙 트리'는 정의상 완전 이진 트리를 사용하는 트리다. 달리 다른 구조를 사용한다 해도 전혀 얻을게 없는 최적의 구조이기 때문.

== 데이터 처리 ==
데이터의 삽입과 삭제는 모두 <math>O(\log N)</math>이 소요된다
.
Heap은 완전 이진트리의 구조를 가지고 있기 때문에 트리의 레벨이 늘어날 수록 노드의 수는 두배씩 증가한다. 
그말은 레벨이 i라고 가정했을때 i레벨의 노드수는 <math>2^{i-1}</math>개이다. (단 i는 마지막 레벨은 아니다. 이는 완전이진트리의 특성때문이다.)
그러므로 트리의 높이는 노드의 수를 통해서 알 수 있다.
트리의 높이는 <math>log_2i+1</math>에서 소수점을 버린값이다.
Heap에서 데이터의 삽입과 삭제는 이 높이와 관련이 있기때문에 빅오 표기법에 의해 <math>O(\log N)</math>이렇게 표현되는 것이다.

=== 데이터 삽입 ===
 1. 가장 끝의 자리에 노드를 삽입한다.
 1. 그 노드와 부모 노드를 서로 비교한다.
 1. 규칙에 맞으면 그대로 두고, 그렇지 않으면 부모와 교환한다. (부모노드는 삽입된 위치의 인덱스 번호에서 /2를 하면 쉽게  구할 수 있다.)
 1. 규칙에 맞을 때까지 3번 과정을 반복한다.

[[파일:4-15-3.png|width=300]]

=== 데이터 삭제 ===
최댓값 혹은 최솟값이 저장된 루트 노드만 제거할 수 있다.
 1. 루트 노드를 제거한다.
 1. 루트 자리에 가장 마지막 노드를 삽입한다.[* 이는 수정될 힙에서 중간에 빈 공간이 생기지 않게 하기 위함이다]
 1. 올라간 노드와 그의 자식 노드(들)와 비교한다.
 1. 조건에 만족하면 그대로 두고, 그렇지 않으면 자식과 교환한다.

  * 최대 힙
   1. 부모보다 더 큰 자식이 없으면 교환하지 않고 끝낸다.
   1. 부모보다 더 큰 자식이 하나만 있으면 그 자식하고 교환하면 된다.
   1. 부모보다 더 큰 자식이 둘 있으면 자식들 중 큰 값과 교환한다.

  * 최소 힙
   1. 부모보다 더 작은 자식이 없으면 교환하지 않고 끝낸다.
   1. 부모보다 더 작은 자식이 하나만 있으면 그 자식하고 교환하면 된다.
   1. 부모보다 더 작은 자식이 둘 있으면 자식들 중 작은 값과 교환한다.

 5. 조건을 만족할 때까지 4의 과정을 반복한다.

[[파일:4-15-4.png|width=300]]


== 표현 ==
[[파일:4-14-12.png|width=500]]

이진 힙은 완전 이진 트리(Complete Binary Tree)로서, 배열로 표현하기 매우 좋은 구조다. 높이 순서대로 순회하면 모든 노드를 배열에 낭비 없이 배치할 수 있기 때문이다. 그림처럼 완전 이진 트리는 배열에 빈틈없이 배치가 가능하며, 대개 트리의 배열 표현의 경우 계산을 편하게 하기 위해 인덱스는 1부터 사용한다.

해당 노드의 인덱스를 알면 깊이가 얼마인지, 부모와 자식 노드가 배열 어디에 위치하는지 바로 알아낼 수 있다. 깊이는 1, 2, 4, 8, ... 순으로 2배씩 증가하며, 인덱스는 1부터 시작했기 때문에 부모/자식 노드의 위치는 각각 부모 [math(\lfloor\frac{i}{2}\rfloor)] , 왼쪽 자식 [math(2i)], 오른쪽 자식 [math(2i+1)]의 간단한 수식으로 계산할 수 있다. 이처럼 해당되는 배열의 인덱스를 금방 찾아낼 수 있다. 물론 꼭 완전 이진 형태가 아니어도 비어있는 위치는 얼마든지 널(Null)로 표현할 수 있기 때문에, 사실상 모든 트리는 배열로 표현이 가능하다.

== 응용 분야 ==
힙의 형태를 보면 최대 힙의 경우 루트가 항상 최댓값이고, 최소 힙의 경우 루트가 항상 최솟값임을 알 수 있다.
이를 이용하여 우선순위 큐(priority queue)를 구현하거나, [[정렬 알고리즘#s-2 2.2|힙 정렬]](heap sort)을 만드는 등의 일을 할 수 있다.
또한 무손실 압축 알고리즘(?)인 [[허프만 코드]]도 힙의 구조를 기반으로 하고있다.

== 코드 ==
=== C++ ===
최소 힙 기준으로 짜인 소스이다.
 * 삽입
{{{#!syntax cpp
void creheap(int *arr2, int key, int input) {
  arr2[key] = input;
  while (key > 1) {
    if (arr2[key] < arr2[key / 2]) {
      swap(arr2[key], arr2[key / 2]);
      key /= 2;
    }
    else break;
  }
}
}}}

 * 삭제
 루트 노드 삭제 후 힙의 마지막 데이터를 가져온 상태를 가정한다.
{{{#!syntax cpp
void delheap(int *arr3, int key, int heap_size) {
  int tmp, nextkey;
  while (heap_size >= key * 2) {
    if (key * 2 + 1 > heap_size && arr3[key * 2] < arr3[key]) {
      swap(arr3[key * 2], arr3[key]);
      key = key * 2;
    }
    else if (key * 2 + 1 > heap_size) break;
    else {
      if (arr3[key * 2] < arr3[key * 2 + 1]) {
        tmp = arr3[key * 2];
        nextkey = key * 2;
      }
      else {
        tmp = arr3[key * 2 + 1];
        nextkey = key * 2 + 1;
      }
      if (tmp < arr3[key]) {
        swap(arr3[key], arr3[nextkey]);
        key=nextkey;
      }
      else break;
    }
  }
}
}}}

[[분류:자료구조]]