[Algorithm] 최소 힙, 최대 힙

[ 힙(Heap)이란? ]

완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해 만든 자료구조이다.

키값이 가장 큰 노드를 찾기 위한 힙을 최대 힙(Max Heap)이라고 하고, 키값이 가장 작은 노드를 찾기 위한 힙을 최소 힙(Min Heap)이라고 한다.

• 최대 힙은 부모 노드의 키값이 자식 노드의 키값보다 항상 크거나 같은 크기의 관계이다.
  • 즉, 부모 노드의 키값 ≥ 자식 노드의 키값의 관계를 가지는 노드들의 완전 이진 트리이다.
  • 최대 힙에서는 키값이 가장 큰 노드가 루트 노드가 된다.
• 최소 힙은 부모 노드의 키값이 자식 노드의 키값보다 항상 작거나 같은 크기의 관계이다.
  • 즉, 부모 노드의 키값 ≤ 자식 노드의 키값의 관계를 가지는 노드들의 완전 이진 트리이다.
  • 최소 힙에서는 키값이 가장 작은 노드가 루트 노드가 된다.

힙은 같은 키값의 노드를 중복해서 가질 수 있으며, 일반적으로 말하는 힙은 최대 힙을 의미한다.

---

[ heapq 모듈 ]

heapq 모듈은 우선순위 큐 알고리즘이라고도 하는 힙(heap) 큐 알고리즘의 구현을 제공한다.

• python의 heapq 모듈은 기본적으로 최소 힙 구조를 이용한다.

1. heap 만들기

✅ 모듈 import

• heap 기능을 사용하려면 heapq 모듈을 import 해줘야 한다.

import heapq

✅ 힙 만드는 방법

힙을 만드는 방법은 2가지가 있다.

1. []로 초기화된 리스트를 사용하기

heap = []

2. 함수 heapify()를 통해 값이 들어 있는 리스트를 힙으로 변환하기

data = [1, 5, 3, 4, 2]
heapq.heapify(data)

• data를 출력해보면 [1, 3, 2, 5, 4]라는 결과를 얻을 수 있다.

---

2. heap 함수 사용하기

✅ heap에 원소 추가하기

heapq.heappush(heap, item)

• 힙 불변성을 유지하면서, item 값을 heap으로 푸시(삽입)한다.

✅ heap에서 원소 삭제하기

heapq.heappop(heap)

• 힙 불변성을 유지하면서, heap에서 가장 작은 항목을 반환한다.
• 힙이 비어 있으면 IndexError가 발생한다.

✅ heap에서 (삭제하지 않고) 가장 작은 원소에 접근하기

heap[0]

• 요소를 제거하지 않고 가장 작은 항목에 접근하려면 heap[0]을 사용하면 된다.

---

3. heap 사용 예제

import heapq

# 힙 선언
heap = []

# 원소 추가하기
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 9)
heapq.heappush(heap, 6)
heapq.heappush(heap, 2)
print('heap:', heap)
print()

# 삭제하지 않고 가장 작은 원소 가져오기
top = heap[0]
print(f'가장 작은 원소: {top}')
print('heap:', heap)
print()

# 원소 삭제하기
a = heapq.heappop(heap)
b = heapq.heappop(heap)
print(f'첫 번째 제거 원소: {a}, 두 번째 제거 원소 {b}')
print('heap:', heap)

• 실행 결과

heap: [1, 2, 9, 6, 5]

가장 작은 원소: 1
heap: [1, 2, 9, 6, 5]

첫 번째 제거 원소: 1, 두 번째 제거 원소 2
heap: [5, 6, 9]

---

[ 최대 힙 ]

최소 힙을 최대 힙처럼 사용하기 위해서는 우선순위에 해당하는 값에 음수 부호 -를 붙인 값과 원래의 값을 튜플 형태로 넣으면 된다.

즉, heapq.heappush(heap, (-item, item))을 이용하여 원소를 추가하면 된다. 실제 원소 값이 두 번째 자리에 저장되어 있으므로 실제 원소 값에 접근할 때는 [1]을 이용하여 heapq.heappop(heap)[1]와 같이 사용하면 된다.

예제 | 최대 힙처럼 사용하기

import heapq

# 힙 선언
heap = []

# 원소 추가하기
heapq.heappush(heap, (-5, 5))
heapq.heappush(heap, (-1, 1))
heapq.heappush(heap, (-9, 9))
heapq.heappush(heap, (-6, 6))
heapq.heappush(heap, (-2, 2))
print('heap:', heap)
print()

# 삭제하지 않고 가장 큰 원소 가져오기
top = heap[0][1]
print(f'가장 큰 원소: {top}')
print('heap:', heap)
print()

# 원소 삭제하기
a = heapq.heappop(heap)[1]
b = heapq.heappop(heap)[1]
print(f'첫 번째 제거 원소: {a}, 두 번째 제거 원소 {b}')
print('heap:', heap)

• 실행 결과

heap: [(-9, 9), (-6, 6), (-5, 5), (-1, 1), (-2, 2)]

가장 큰 원소: 9
heap: [(-9, 9), (-6, 6), (-5, 5), (-1, 1), (-2, 2)]

첫 번째 제거 원소: 9, 두 번째 제거 원소 6
heap: [(-5, 5), (-2, 2), (-1, 1)]

---

[ 📘 Reference ]

C로 배우는 쉬운 자료구조 - 한빛아카데미
https://docs.python.org/ko/3/library/heapq.html
이것이 코딩테스트다 with 파이썬 책