heapq
heapq
deque처럼 deque객체를 생성하는 것이 아니라 list를 최소힙처럼 다룰 수 있도록 도와준다.
heqpq모듈을 통해 원소를 추가하거나 삭제하면 해당 리스트는 최소힙 성질을 가지게 된다.
- heappush: 첫번째 파라미터는 원소를 추가할 대상 리스트, 두번째 파라미터는 추가할 원소
- heappop: 파라미터로 넘겨 받은 리스트의 가장 작은 원소를 삭제, 리턴
내부적으로 이진 트리에 원소를 추가, 삭제하므로 두 함수 모두 \(O(logn)\)의 시간 복잡도를 가진다.
# heapq를 이용한 힙정렬 구현
import heapq
def heapsort_min(arr):
h = []
result = []
# 힙에 삽입
for value in arr:
heapq.heappush(h, value)
# 힙에서 꺼내서 담기
for i in range(len(h)):
result.append(heapq.heappop(h))
return result
def heapsort_max(arr): # heapq 라이브러리는 최대힙을 제공하지 않음
h = []
result = []
# 힙에 삽입
for value in arr:
heapq.heappush(h, -value)
# 힙에서 꺼내서 담기
for i in range(len(h)):
result.append(-heapq.heappop(h))
return result
arr = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
result = heapsort_min(arr)
print(result)
result = heapsort_max(arr)
print(result)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
- heapify: 이미 원소가 존재하는 리스트가 힙 구조에 맞게 재배치
\(O(n)\)의 시간 복잡도를 가진다.
arr = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
heapq.heapify(arr)
print(arr)
[0, 1, 2, 6, 3, 5, 4, 7, 8, 9]
- nsmallest, nlargest: 가장 작은 n개의 값, 가장 큰 n개의 값을 리스트로 반환
arr = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
print('가장 작은 값 3개:', heapq.nsmallest(3, arr))
print('3번째 작은 값:', heapq.nsmallest(3, arr)[-1])
가장 작은 값 3개: [0, 1, 2]
3번째 작은 값: 2
arr = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
print('가장 큰 값 3개:', heapq.nlargest(3, arr))
print('3번째 큰 값:', heapq.nlargest(3, arr)[-1])
가장 큰 값 3개: [9, 8, 7]
3번째 큰 값: 7
Reference
- DaleSeo : 파이썬의 heapq 모듈로 힙 자료구조 사용하기
댓글남기기