힙(Heap)

개요

힙(Heap)은 완전 이진 트리 기반의 자료구조로, 부모 노드와 자식 노드 간의 우선순위 조건을 만족하는 구조이다. 최소 힙(Min Heap)은 부모 노드 ≤ 자식 노드, 최대 힙(Max Heap)은 부모 노드 ≥ 자식 노드의 조건을 만족한다. 주로 **우선순위 큐(Priority Queue)**로 활용되며, 삽입/삭제 모두 평균 O(log n)의 성능을 제공한다.

---

1. 힙의 구조 및 특징

항목	설명
트리 구조	완전 이진 트리(왼쪽부터 채움)
힙 조건	부모 노드 ≥ 자식 노드 (최대 힙), ≤ (최소 힙)
저장 방식	배열 인덱스 기반 표현 (root: index 0)
사용 용도	우선순위 큐, 정렬 알고리즘 (Heap Sort) 등

---

2. 힙의 배열 표현

노드 위치	인덱스 관계
부모 노드	i
왼쪽 자식	2i + 1
오른쪽 자식	2i + 2
부모 접근	(i - 1) // 2

힙은 배열로 구현하되 트리 구조로 해석하는 방식이다.

---

3. 힙의 종류

유형	설명	예시
최소 힙 (Min Heap)	루트가 가장 작은 값	우선순위 낮은 값 우선 처리
최대 힙 (Max Heap)	루트가 가장 큰 값	우선순위 높은 값 우선 처리
이진 힙 (Binary Heap)	완전 이진 트리 기반 일반 힙
피보나치 힙	이론적으로 삽입 O(1), 삭제 O(log n)

---

4. 파이썬 힙 구현 예시 (heapq)

import heapq

# 최소 힙
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 8)
print(heapq.heappop(min_heap))  # 출력: 3

# 최대 힙 구현 (음수 활용)
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -3)
print(-heapq.heappop(max_heap))  # 출력: 5

---

5. 시간 및 공간 복잡도

연산	시간 복잡도
삽입 (heappush)	O(log n)
삭제 (heappop)	O(log n)
힙 구성 (heapify)	O(n)

공간 복잡도는 O(n), 힙 자체는 배열로 저장된다.

---

6. 힙의 활용 사례

분야	예시
우선순위 큐	작업 스케줄링, 실시간 처리
다익스트라 알고리즘	최소 비용 정점 선택 시 사용
힙 정렬	힙을 기반으로 한 O(n log n) 정렬
K번째 요소 찾기	최소/최대 힙으로 최적화
온라인 통계	중간값 유지(Median Maintenance)

---

7. 힙 vs 이진 탐색 트리(BST)

항목	힙	이진 탐색 트리
정렬 순서	부모 ≥/≤ 자식	왼쪽 < 루트 < 오른쪽
순회 순서	정렬 불가능	중위 순회 시 정렬
삽입/삭제	O(log n)	O(log n) (균형 트리일 때)
구현 용이성	배열 기반, 간단	포인터 기반, 복잡할 수 있음

---

8. 결론

힙은 우선순위 기반 작업 처리를 위해 설계된 효율적인 트리형 자료구조로, 삽입과 삭제 연산이 빠르고, 다양한 알고리즘과 실무 로직에서 핵심 역할을 한다. 배열로 구현되며, 힙 정렬, 다익스트라, 작업 스케줄링 등 수많은 문제 해결에 활용된다. 최소 힙과 최대 힙의 특성을 이해하고 적절히 활용할 수 있어야 한다.