[자료구조/Python] 힙, heapq 모듈의 모든것

PhilAI·2023년 8월 5일

코테 공부 기록을 담고 있어요 📝

목록 보기

4/32

파이썬의 heapq 모듈을 활용하여 힙 자료구조와 힙큐(heapq)를 사용하는 방법에 대해 알아보겠습니다. 힙은 최소값 또는 최대값을 빠르게 찾기 위한 이진트리 기반의 자료구조로, 우선순위 큐를 구현하는데 사용됩니다. 파이썬의 heapq 모듈은 효율적인 힙 기능을 제공하여 데이터를 관리하고 처리하는데 유용하게 활용됩니다.

힙 자료구조란?

힙은 이진트리를 기반으로 한 자료구조로, 노드들 간의 부모-자식 관계를 이용하여 정렬된 트리 구조를 만듭니다. 최소 힙(min heap)은 부모 노드의 값이 자식 노드보다 항상 작거나 같으며, 최대 힙(max heap)은 부모 노드의 값이 자식 노드보다 항상 크거나 같습니다.

heapq 모듈

파이썬의 heapq 모듈은 이진힙 기능을 제공하며, 리스트를 힙 자료구조로 변환하고 원소를 추가하거나 삭제하는 함수를 제공합니다.

우선, heapq 모듈을 import하여 사용합니다.

import heapq

heapq 기본 사용법

1. 리스트를 힙으로 변환하기

heapq 모듈의 heapify 함수를 사용하여 기존 리스트를 힙으로 변환할 수 있습니다. 이 함수를 사용하면 리스트의 원소들이 힙 속성을 만족하도록 재배치됩니다.

data_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(data_list)
print(data_list)  # 출력 결과: [1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

2. 원소 추가하기

heapq 모듈의 heappush 함수를 사용하여 힙에 원소를 추가할 수 있습니다.

data_list = [3, 1, 4]
heapq.heapify(data_list)
print(data_list)  # 출력 결과: [1, 3, 4]

# 원소 2를 힙에 추가
heapq.heappush(data_list, 2)
print(data_list)  # 출력 결과: [1, 2, 4, 3]

3. 최솟값 확인하기

eapq 모듈의 heappop 함수를 사용하여 힙에서 최솟값을 가져올 수 있습니다. 이때, 힙에서 최솟값이 제거됩니다.

data_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(data_list)

min_value = heapq.heappop(data_list)
print(min_value)  # 출력 결과: 1
print(data_list)  # 출력 결과: [1, 3, 2, 5, 5, 9, 4, 6, 5, 3]

4. 최대 힙 활용하기

기본적으로 heapq 모듈은 최소 힙을 지원합니다. 하지만 최대 힙을 사용하려면 원소의 부호를 반대로 바꾸어 넣은 후, 값을 꺼낼 때 다시 부호를 바꾸는 방식으로 구현할 수 있습니다.

data_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

# 원소의 부호를 반대로 바꾸어 최대 힙으로 사용
data_list = [-x for x in data_list]
heapq.heapify(data_list)

# 최댓값 확인 및 추출 (부호를 다시 바꿔서 양수로 표현)
max_value = -heapq.heappop(data_list)
print(max_value)  # 출력 결과: 9