PYTHON

파이썬에서의 힙(Heap)과 힙큐(heapq) 활용법

DevMaster!! 2024. 8. 17. 22:19

힙(Heap)은 우선순위 큐를 구현하는 데 사용되는 자료구조로, 최댓값 또는 최솟값을 빠르게 찾아내는 데 매우 효율적입니다. 파이썬에서는 heapq 모듈을 사용하여 힙을 쉽게 구현할 수 있습니다. 이번 글에서는 힙의 기본 개념과 heapq 모듈을 활용하여 힙을 사용하는 방법을 알아보겠습니다.

1. 힙(Heap)이란?

힙은 완전 이진 트리(Complete Binary Tree) 구조를 가지며, 각 노드는 자식 노드보다 크지 않거나 작지 않은 특성을 가지고 있습니다. 힙은 크게 두 가지로 나눌 수 있습니다:

  1. 최소 힙(Min-Heap): 부모 노드가 자식 노드보다 작거나 같은 값을 가지는 힙. 루트 노드에는 최솟값이 위치합니다.
  2. 최대 힙(Max-Heap): 부모 노드가 자식 노드보다 크거나 같은 값을 가지는 힙. 루트 노드에는 최댓값이 위치합니다.

파이썬의 heapq 모듈은 최소 힙을 기본으로 제공하며, 최대 힙은 일부 변형을 통해 구현할 수 있습니다.

1.1. 힙의 특성

  • 삽입: 힙에 새로운 요소를 삽입할 때는 트리의 마지막 위치에 추가한 후, 부모 노드와 비교하여 적절한 위치로 이동시킵니다.
  • 삭제: 힙에서 최솟값 또는 최댓값을 삭제할 때는 루트 노드를 제거하고, 트리의 마지막 노드를 루트로 이동한 후, 자식 노드와 비교하여 적절한 위치로 이동시킵니다.

힙의 삽입과 삭제 연산의 시간 복잡도는 O(log n)입니다.

2. heapq 모듈 소개

파이썬의 heapq 모듈은 힙 자료구조를 구현하기 위한 여러 가지 유용한 함수들을 제공합니다. heapq 모듈을 사용하면 리스트를 최소 힙으로 다룰 수 있습니다.

2.1. heapq 모듈의 주요 함수

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

3. heapq 모듈 사용 예시

3.1. 힙에 요소 추가 및 제거

import heapq

# 빈 힙 생성
heap = []

# 힙에 요소 추가
heapq.heappush(heap, 10)
heapq.heappush(heap, 30)
heapq.heappush(heap, 20)
heapq.heappush(heap, 40)

print("Heap:", heap)  # 출력: Heap: [10, 30, 20, 40]

# 힙에서 가장 작은 요소 제거
min_element = heapq.heappop(heap)
print("Popped element:", min_element)  # 출력: Popped element: 10
print("Heap after pop:", heap)  # 출력: Heap after pop: [20, 30, 40]

위 코드에서 heapq.heappush를 사용하여 힙에 요소를 추가하고, heapq.heappop을 사용하여 힙에서 가장 작은 요소를 제거할 수 있습니다.

3.2. 기존 리스트를 힙으로 변환

import heapq

# 기존 리스트
numbers = [20, 10, 40, 30]

# 리스트를 힙으로 변환
heapq.heapify(numbers)
print("Heapified list:", numbers)  # 출력: Heapified list: [10, 20, 40, 30]

# 힙에서 가장 작은 요소 제거
min_element = heapq.heappop(numbers)
print("Popped element:", min_element)  # 출력: Popped element: 10

위 코드에서는 heapq.heapify를 사용하여 기존 리스트를 힙으로 변환합니다. 변환 후, 리스트는 최소 힙의 속성을 가지게 됩니다.

3.3. 최대 힙 구현

파이썬의 heapq 모듈은 기본적으로 최소 힙을 제공합니다. 최대 힙을 구현하려면 삽입 시 요소의 부호를 바꿔주고, 제거할 때 다시 부호를 바꿔주면 됩니다.

import heapq

# 빈 힙 생성
max_heap = []

# 힙에 요소 추가 (부호를 반대로 하여 최대 힙 구현)
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -30)
heapq.heappush(max_heap, -20)
heapq.heappush(max_heap, -40)

print("Max Heap:", [-x for x in max_heap])  # 출력: Max Heap: [40, 30, 20, 10]

# 힙에서 가장 큰 요소 제거
max_element = -heapq.heappop(max_heap)
print("Popped element:", max_element)  # 출력: Popped element: 40
print("Max Heap after pop:", [-x for x in max_heap])  # 출력: Max Heap after pop: [30, 10, 20]

위 코드에서 요소를 삽입할 때 부호를 반대로 하여 최대 힙을 구현했습니다.

3.4. 힙을 사용한 k번째 최소 또는 최대 요소 찾기

힙은 특정 순위에 해당하는 요소를 효율적으로 찾는 데 유용합니다. 예를 들어, 리스트에서 k번째로 작은 요소를 찾으려면 최소 힙을 사용하여 k번 요소를 제거하면 됩니다.

import heapq

def find_kth_smallest(numbers, k):
    heapq.heapify(numbers)
    for _ in range(k - 1):
        heapq.heappop(numbers)
    return heapq.heappop(numbers)

numbers = [7, 10, 4, 3, 20, 15]
k = 3
result = find_kth_smallest(numbers, k)
print(f"{k}rd smallest element is {result}")  # 출력: 3rd smallest element is 7

위 코드에서 find_kth_smallest 함수는 힙을 사용하여 리스트에서 k번째로 작은 요소를 찾아 반환합니다.

4. 힙의 활용 사례

힙은 다양한 알고리즘과 문제 해결에 사용됩니다. 대표적인 활용 사례는 다음과 같습니다:

  • 우선순위 큐: 힙은 우선순위 큐를 구현하는 데 적합합니다. 예를 들어, 다익스트라 알고리즘에서 최소 비용 경로를 찾을 때 사용됩니다.
  • 정렬: 힙 정렬(Heap Sort)은 힙을 이용한 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가집니다.
  • k번째 최소/최대 요소 찾기: 위에서 설명한 것처럼 힙을 사용하여 특정 순위에 해당하는 요소를 효율적으로 찾을 수 있습니다.

결론

이번 글에서는 파이썬에서 힙 자료구조와 heapq 모듈을 사용하여 힙을 구현하는 방법을 살펴보았습니다. 힙은 우선순위 큐, 정렬, 특정 순위 요소 찾기 등 다양한 문제를 해결하는 데 매우 유용한 자료구조입니다. heapq 모듈을 사용하여 힙을 쉽게 구현하고, 다양한 문제 해결에 활용해보세요.

이 글을 통해 파이썬의 힙 자료구조와 heapq 모듈에 대해 이해하고, 이를 활용하는 방법을 익힐 수 있을 것입니다. 힙을 적절히 활용하여 효율적인 알고리즘과 데이터 처리를 구현해 보세요!