[Algorithm] 최소 힙(Min Heap)

---

최소 힙

최소 힙(Min Heap)은 이진 트리 형태의 자료구조로, 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같은 특성을 갖는 구조이다.

• O(logn)의 시간 복잡도로 삽입/삭제 가능
• 작은 값을 효율적으로 관리 가능
• 특정 값 삭제, 임의 인덱스 접근이 비효율적. O(n)이 소요됨

특징

• 부모 ≤ 자식
  • 모든 부모 노드의 값은 자식 노드의 값보다 작거나 같다.
  • 가장 작은 값이 루트 노드에 위치.
• 완전 이진 트리
  • 트리의 모든 레벨이 꽉 차 있으며, 마지막 레벨은 왼쪽부터 채워져야 함.

활용

최소 힙은 최솟값을 효율적으로 찾거나 관리해야 하는 상황에서 유용하다.

• 우선순위 큐 구현
• 정렬되지 않은 데이터에서 최솟값 추출
• 데이터 스트림에서 k번째 작은 값 유지

 

연산

• 삽입 O(log⁡n)
  • 새 데이터를 트리의 가장 아래(왼쪽부터 채움)에 삽입.
  • 부모와 비교하여 올바른 위치에 도달할 때까지 값을 교환(Heapify-Up).
• 최솟값 삭제 O(log⁡n)
  • 루트 노드(최솟값)를 제거.
  • 가장 마지막 노드를 루트로 이동한 후, 자식과 비교하며 교환(Heapify-Down).
• 최솟값 조회 O(1)
  • 루트 노드 값 반환 

 

구현 방식

최소 힙은 배열로 효율적으로 구현할 수 있다

• 인덱스 관계
  • 부모 인덱스 : i
  • 왼쪽 자식 : 2i + 1
  • 오른쪽 자식: 2i + 2

 

예제

1. 입력 데이터 : [5, 3, 8, 1, 2]
2. 삽입 순서대로 최소 힙 생성
   • 5 삽입 → [5]
   • 3 삽입 → [3, 5]
   • 8 삽입 → [3, 5, 8]
   • 1 삽입 → [1, 3, 8, 5] (1과 3 교환)
   • 2 삽입 → [1, 2, 8, 5, 3] (2과 3 교환)
3. 최솟값(1) 제거
   • [2, 3, 8, 5] (루트 노드 1 제거 후 2를 루트로 이동)

 

파이썬에서 최소 힙 사용

파이썬의 heapq 모듈은 기본적으로 최소 힙을 제공하며, 다음과 같은 연산을 지원한다.

import heapq

heap = []
heapq.heappush(heap, 5)  # 삽입
heapq.heappush(heap, 3)
heapq.heappush(heap, 8)

print(heapq.heappop(heap))  # 최솟값 제거 → 3
print(heap[0])  # 최솟값 확인 → 5

 

---