[Python]힙(Heap)

---

힙(Heap)이란?

힙은 이진 트리의 한 형태로, 다음과 같은 특징을 가집니다:

• 최대 힙(Max Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같은 구조.
• 최소 힙(Min Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같은 구조.

파이썬의 heapq 모듈은 최소 힙(Min Heap)을 기본으로 합니다.

---

힙을 사용하는 이유

힙은 주로 다음과 같은 상황에서 사용됩니다:

1. 우선순위 큐(Priority Queue): 힙을 사용하면 높은 우선순위를 가진 요소를 빠르게 찾을 수 있습니다.

2. 최소값/최대값 탐색: 힙 구조에서는 최소값 또는 최대값을 빠르게 찾을 수 있습니다.

3. 정렬: 힙 정렬(Heap Sort)을 통해 정렬 작업을 수행할 수 있습니다.

---

힙 사용법

파이썬에서는 heapq 모듈을 사용하여 힙을 쉽게 구현할 수 있습니다. 기본적으로 리스트를 힙으로 변환하여 사용합니다.

import heapq

# 리스트를 힙으로 변환
heap = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(heap)
print(heap)  # [1, 1, 2, 3, 5, 9, 4, 6, 5, 3, 5]

---

힙 내장 함수

heapq 모듈에서 제공하는 주요 함수들은 다음과 같습니다:

• heapq.heappush(heap, item): 힙에 새로운 요소를 추가합니다.
• heapq.heappop(heap): 힙에서 가장 작은 요소를 제거하고 반환합니다.
• heapq.heapify(iterable): 주어진 iterable을 힙으로 변환합니다.
• heapq.heappushpop(heap, item): 힙에 새로운 요소를 추가한 후 가장 작은 요소를 제거하고 반환합니다.
• heapq.heapreplace(heap, item): 힙에서 가장 작은 요소를 제거하고, 새로운 요소를 추가합니다.

---

힙 사용 예제

1. 우선순위 큐: 작업의 우선순위를 관리할 때

import heapq

tasks = [(1, 'Write code'), (3, 'Release product'), (2, 'Test application')]
heapq.heapify(tasks)

while tasks:
    priority, task = heapq.heappop(tasks)
    print(f'Priority: {priority}, Task: {task}')

2. 최소값/최대값 찾기: 배열에서 k번째 작은 요소 찾기

import heapq

nums = [4, 1, 7, 3, 8, 5]
k = 3
heapq.heapify(nums)

for _ in range(k - 1):
    heapq.heappop(nums)

print(heapq.heappop(nums))  # k번째 작은 값

힙을 사용할 때 주의할 점

1. 기본 제공 힙은 최소 힙: 최대 힙이 필요하다면 요소의 부호를 반전시켜 사용할 수 있습니다.
2. 자료형 혼합 주의: 힙 내에서는 동일한 자료형을 사용하는 것이 좋습니다.
3. 히프리스트의 직접 수정 금지: heapq 모듈을 통해서만 힙을 수정해야 힙의 속성이 유지됩니다.

힙은 다양한 알고리즘과 데이터 구조에서 중요한 역할을 하며, 이를 효율적으로 활용할 수 있다면 많은 문제를 쉽게 해결할 수 있습니다. 이번 글을 통해 파이썬에서 힙을 사용하는 방법을 이해하고, 실전에서 활용해 보세요.