이진 힙
정의
이진 힙(binary heap)은 완전 이진 트리(complete binary tree)를 기반으로 한 우선순위 큐(priority queue)의 일종이다. 각 노드는 키(key) 값을 가지며, 부모 노드와 자식 노드 간에 힙 속성(heap property)이 유지된다. 힙 속성에는 두 종류가 있다.
- 최대 힙(max‑heap): 각 부모 노드의 키 값이 자식 노드들의 키 값보다 크거나 같다.
- 최소 힙(min‑heap): 각 부모 노드의 키 값이 자식 노드들의 키 값보다 작거나 같다.
이러한 속성으로 인해 트리의 루트(root)에는 전체 원소 중 최대값(또는 최소값)이 저장된다.
구조
- 완전 이진 트리: 모든 레벨이 왼쪽에서 오른쪽으로 채워진 형태이며, 마지막 레벨만 부분적으로 채워질 수 있다. 이 특성 때문에 이진 힙은 배열(array)로 효율적으로 구현할 수 있다.
- 배열 인덱싱:
- 부모 노드 인덱스
i에 대해 왼쪽 자식은2i + 1, 오른쪽 자식은2i + 2. - 자식 인덱스
i에 대해 부모는(i‑1) // 2.
- 부모 노드 인덱스
주요 연산 및 시간 복잡도
| 연산 | 설명 | 최악 시간 복잡도 |
|---|---|---|
insert (삽입) |
새로운 원소를 힙의 마지막 위치에 추가한 뒤, 상향 힙화(up‑heap)(또는 부모와 비교하여 위로 이동)를 수행 | O(log n) |
extract‑max / extract‑min |
루트(최대/최소값)를 제거하고, 마지막 원소를 루트에 놓은 뒤 하향 힙화(down‑heap)(또는 자식과 비교하여 아래로 이동)를 수행 | O(log n) |
peek (최대/최소값 조회) |
루트 값을 바로 반환 | O(1) |
increase‑key / decrease‑key |
지정된 원소의 키 값을 변경하고, 필요에 따라 상향 또는 하향 힙화를 수행 | O(log n) |
heapify (배열을 힙으로 변환) |
주어진 배열을 힙 구조로 재구성 | O(n) |
구현 방식
- 배열 기반 구현: 위의 인덱스 관계를 이용해 메모리 오버헤드 없이 구현한다. 대부분의 프로그래밍 언어 표준 라이브러리(예: C++
std::priority_queue, JavaPriorityQueue, Pythonheapq)는 배열 기반 이진 힙을 사용한다. - 포인터 기반 트리 구현: 직접 노드 객체를 연결하여 구현할 수 있지만, 배열에 비해 메모리 사용량이 늘어나고 인덱스 연산이 필요 없어지는 장점은 제한적이다.
활용 예시
- 다익스트라 최단 경로 알고리즘: 우선순위 큐로 사용하여 최소 거리 정점을 효율적으로 선택.
- 힐 파일 정렬(Heapsort): 배열을 힙으로 만든 뒤 차례로 최대값을 꺼내어 정렬.
- 스케줄링 및 작업 관리: 가장 높은 우선순위 작업을 빠르게 선택.
- 실시간 스트림 처리: 상위 K개 원소 유지(예:
K-largest elements) 등에 활용.
변형 및 관련 자료구조
- 피보나치 힙(Fibonacci heap), 이항 힙(binomial heap) 등은 삽입·병합·감소 연산에서 보다 좋은 이론적 복잡도를 제공하지만, 실제 구현·성능 면에서는 이진 힙보다 복잡하다.
- 우선순위 큐: 이진 힙 외에도 배열 기반 힙, 트리 기반 힙, 스킵 리스트 등 다양한 구현체가 존재한다.
역사·참고 문헌
- 이진 힙의 개념은 1964년 J. W. J. Williams가 제안한 힙 정렬(Heap Sort) 논문에서 처음 소개되었다. 이후 C. L. Lloyd가 1966년에 우선순위 큐 구현에 적용한 것이 널리 알려졌다.
- 주요 교과서:
- Cormen, Thomas H. Introduction to Algorithms (3rd ed.) – Chapter 6 (Heapsort).
- Sedgewick, Robert; Wayne, Kevin. Algorithms (4th ed.) – Section on priority queues.
요약
이진 힙은 완전 이진 트리 구조와 힙 속성을 이용해 삽입·삭제·조회 등 우선순위 큐 연산을 로그 시간에 수행할 수 있는 효율적인 자료구조이다. 배열 기반 구현이 일반적이며, 다양한 알고리즘 및 시스템에서 핵심 구성 요소로 사용된다.
