힙(heap)

힙(heap)

힙은 일종의 완전 이진트리(complete binary tree)로 구현되며, 최대값 혹은 최소값을 빠르게 찾아내는 자료구조이다. 최대값을 찾는 경우에는 최대 힙(max heap), 최소값을 찾는 경우에는 최소 힙(min heap) 이라고 한다. 

 

이진트리, 완전 이진트리, 포화 이진트리
이진트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리를 말한다. 완전 이진트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽부터 채워져 있는 상태를 말한다. 포화 이진트리는 마지막 자식 레벨도 꽉 채워진 상태를 말함.

 

힙에서는 각 노드가 특정 조건을 만족해야 한다. 최대 힙의 경우, 모든 노드는 그 자식 노드들보다 큰 값을 갖는다. 최소 힙의 경우, 모든 노드는 그 자식 노드들 보다 작은 값을 갖는다. 이러한 조건을 힙 속성(heap prorerty) 이라고 한다. 또한, 힙은 반정렬 상태로 형제 노드간에 중복 값을 허용을 하고 있다.

---

힙의 구현

완전 이진트리의 속성을 이용 하여 힙은 배열의 인덱스로 구현이 가능하다. 각 노드의 인덱스가 i 라고 할 때, 그 노드의 부모 노드 인덱스는 (i /2 -1) 이고, 왼쪽 자식 노드 인덱스는 (2i + 1), 오른쪽 자식 노드 인덱스는 (2i + 2) 이다. 0번 인덱스를 비워 두고 사용하면 부모 노드 인덱스는 (i /2 ) 이고, 왼쪽 자식 노드 인덱스는 (2i ), 오른쪽 자식 노드 인덱스는 (2i + 1) 이다.

배열 시작 index가 0부터 일때

배열의 시작 index가 1부터 일때

힙에 새로운 값을 추가할 때는 일단 새로운 값을 배열의 가장 마지막 노드에 추가한 후, 부모 노드와 비교하여 힙 속성을 유지하면서 위치를 조정한다. 최대 힙의 경우, 새로운 값이 부모 노드보다 크다면 두 노드의 위치를 바꿔주고, 최소 힙의 경우 반대로 새로운 값이 부모 모드보다 작으면 두 노드의 위치를 바꿔주면 된다.     

값 추가시

값 삭제시

---

힙의 활용

힙은 우선순위 큐(priority queue) 를 구현하는 데 주로 사용이 된다. 우선순위 큐는, 우선순위가 높은 요소가 먼저 처리되는 자료구조를 말한다. 예를 들어, 작업 스케쥴링, 이벤트 처리, 네트워크 처리 등에 사용된다. 

 

힙은 또한 정렬 알고리즘에서도 활용이 되고 있다. 힙 정렬(heap sort)은 정렬 알고리즘 중 하나로, 최소 힙을 이용하여 정렬을 수행한다.