힙(Heap)은 트리 알고리즘 중 하나로, 자료를 저장하고 효율적으로 관리하는 데 사용됩니다. 힙은 가장 큰 값이나 가장 작은 값에 빠르게 접근할 수 있는 자료구조로, 주로 우선순위 큐(Priority Queue)에서 사용됩니다. 이번 포스트에서는 힙을 파이썬으로 구현하는 방법과 응용 예제를 다룰 것입니다.

힙의 기본 개념

힙은 ‘완전 이진 트리’라는 특성을 가지고 있습니다. 이는 모든 노드가 왼쪽 자식부터 차례대로 채워진 이진 트리를 말합니다. 또한, 힙은 다음과 같은 조건을 만족해야 합니다.

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

힙의 구현

파이썬에서 힙은 heapq 라이브러리를 사용하여 구현할 수 있습니다. heapq는 최소 힙을 구현하는 데에 사용되며, 최대 힙을 구현하려면 부호를 반대로 저장해야 합니다.

import heapq

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

# 힙에 원소 추가
heapq.heappush(data, 9)

# 최소값 삭제 후 반환
min_value = heapq.heappop(data)

print(min_value)  # 출력: 1

힙의 응용

힙은 우선순위 큐(Priority Queue)를 구현할 때 가장 많이 사용됩니다. 우선순위 큐는 항목이 추가되거나 삭제될 때마다 우선순위 순서에 따라 항목을 정렬하는 자료구조입니다. 힙을 사용하여 우선순위 큐를 구현하기 위해서는 아래와 같은 방법을 사용할 수 있습니다.

import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []

    def push(self, item, priority):
        heapq.heappush(self.heap, (priority, item))

    def pop(self):
        _, item = heapq.heappop(self.heap)
        return item

    def is_empty(self):
        return len(self.heap) == 0

# 우선순위 큐 사용 예제
pq = PriorityQueue()
pq.push("Task 1", 3)
pq.push("Task 2", 1)
pq.push("Task 3", 2)

while not pq.is_empty():
    task = pq.pop()
    print(task)  # 출력: Task 2, Task 3, Task 1 (우선순위 순서대로)

이처럼 힙을 활용하여 우선순위 큐를 구현하면, 다양한 응용에 활용할 수 있습니다.

결론

이번 포스트에서는 트리 알고리즘인 힙(Heap)에 대해 알아보았습니다. 힙은 자료를 효율적으로 관리하는 데 사용되며, 주로 우선순위 큐에서 활용됩니다. 파이썬의 heapq 라이브러리를 사용하여 힙을 구현할 수 있으며, 우선순위 큐를 구현하기 위해서도 힙을 활용할 수 있습니다. 힙을 잘 이해하고 활용하면 다양한 문제를 효율적으로 해결할 수 있습니다.