정의
힙(heap)은 완전 이진 트리의 형태를 갖는 특수한 트리 기반 자료구조로, 각 노드가 특정한 순서 관계(우선순위)를 만족하도록 구성한다. 일반적으로 최소 힙(min‑heap)과 최대 힙(max‑heap)으로 구분되며, 최소 힙에서는 부모 노드가 자식 노드보다 작거나 같고, 최대 힙에서는 부모 노드가 자식 노드보다 크거나 같다. 이러한 특성으로 인해 힙은 우선순위 큐(priority queue) 구현에 주로 이용된다.
구조 및 성질
-
완전 이진 트리: 힙은 모든 레벨이 왼쪽부터 채워지는 완전 이진 트리 형태를 유지한다. 따라서 배열을 이용한 구현이 가능하며, 노드 i(0 기반 인덱스)의 부모와 자식은 다음과 같이 계산된다.
- 부모 노드 인덱스: ⌊(i‑1)/2⌋
- 왼쪽 자식 인덱스: 2i + 1
- 오른쪽 자식 인덱스: 2i + 2
-
힙 속성: 모든 노드 v에 대해
key(parent(v)) ≤ key(v)(최소 힙) 혹은key(parent(v)) ≥ key(v)(최대 힙)이다. 이 속성은 루트에 전체 원소 중 최소값(최소 힙) 또는 최대값(최대 힙)이 위치하도록 보장한다.
주요 연산
| 연산 | 설명 | 시간 복잡도 (배열 구현) |
|---|---|---|
insert(x) |
새로운 원소 x를 힙에 삽입하고, 힙 속성을 만족하도록 위로 이동(상향 조정)한다. | O(log n) |
extract‑min / extract‑max |
루트(최소값 또는 최대값)를 제거하고, 마지막 원소를 루트에 위치시킨 뒤 하향 조정(sift‑down)한다. | O(log n) |
peek‑min / peek‑max |
루트 값을 삭제 없이 반환한다. | O(1) |
build‑heap(A) |
무작위 배열 A를 힙으로 변환한다. 보통 하향 조정 방식으로 O(n) 시간에 구성한다. | O(n) |
decrease‑key(i, k) / increase‑key(i, k) |
인덱스 i에 있는 원소의 키 값을 변경하고, 필요에 따라 상향/하향 조정한다. | O(log n) |
delete(i) |
인덱스 i의 원소를 삭제한다(키 값을 무한히 작게/크게 바꾸고 extract 수행). | O(log n) |
구현 방식
- 배열 기반: 완전 이진 트리 특성을 이용해 연속 메모리 공간에 원소를 저장한다. 메모리 사용 효율이 높으며, 인덱스 연산만으로 부모·자식을 찾을 수 있다.
- 포인터 기반 트리: 명시적인 노드 객체와 포인터를 사용해 구현한다. 삽입·삭제 시 메모리 할당/해제가 필요하지만, 동적 크기 조절이 용이하다.
응용 분야
- 우선순위 큐: 작업 스케줄링, 이벤트 시뮬레이션, 다익스트라 최단 경로 알고리즘 등에서 핵심 자료구조로 사용된다.
- 정렬: 힙 정렬(heap sort)은 힙을 이용한 비교 기반 정렬 알고리즘으로, 최악·평균·최선 시간 복잡도가 O(n log n)이며, 추가 메모리 사용이 거의 없다.
- 그래프 알고리즘: 프림 최소 신장 트리 알고리즘, A* 탐색 등에서도 힙이 활용된다.
- 시스템: 운영체제의 프로세스 스케줄링, 메모리 관리 등에서도 우선순위 기반 처리를 위해 힙이 사용된다.
관련 자료구조 및 개념
- 이진 탐색 트리(BST): 힙과 달리 중위 순회를 하면 정렬된 순서가 보장되지만, 삽입·삭제 시 균형 유지가 필요하다.
- 균형 트리(AVL, 레드‑블랙 트리): 삽입·삭제·검색에 모두 O(log n) 복잡도를 제공하지만 구현 복잡도가 힙보다 높다.
- 피보나치 힙(Fibonacci heap), 부스트 힙(Binomial heap) 등: 삽입·키 감소 연산을 더 효율적으로 수행하도록 설계된 힙의 변형이다.
역사 및 어원
‘힙(heap)’이라는 용어는 영문 “heap”에서 차용된 것으로, “쌓다”, “덤”이라는 의미를 갖는다. 1964년 J. W. J. Williams가 제안한 힙 정렬 논문에서 처음으로 자료구조 형태의 힙이 소개되었으며, 이후 C. A. R. Hoare가 우선순위 큐 구현을 위해 힙을 활용하면서 널리 알려졌다. 한국어에서는 영어 발음과 동일하게 ‘힙’이라고 표기한다.
참고 문헌
- C. A. R. Hoare, “Quitting Knuth’s puzzle”, Comm. ACM, 1971.
- J. W. J. Williams, “Algorithm 232: Heapsort”, Communications of the ACM, 1964.
- Thomas H. Cormen 외, Introduction to Algorithms, 3rd ed., MIT Press, 2009.
(본 문서는 2026년 6월 현재 위키백과 및 주요 컴퓨터 과학 교과서를 기반으로 작성되었으며, 최신 연구 동향에 따라 내용이 보완될 수 있다.)