우선순위 큐(PriorityQueue)
파이썬 우선순위 큐 구현에서 heapq가 PriorityQueue보다 실행시간이 적게 걸려 heapq를 일반적으로 많이 사용한다.
힙 자료구조
heapq 모듈은 이진트리 기반의 최소 힙 자료구조를 제공합니다.
min heap을 사용하면 원소들이 항상 정렬된 상태로 추가되고 삭제되며,min heap에서 가장 작은 값은 언제나 인덱스 0, 즉, 이진트리의 루트에 위치합니다.
heaqp는 list와 tree의 장점을 모두 사용합니다.
1. 트리구조를 사용합니다.
요소 삽입 및 최소값의 제거 시 발생하는 요소의 검색 및 스왑의 횟수가 일반적인 리스트를 사용할때 보다 현저히 적다.
- 리스트를 사용합니다.
완전 이진트리는 리스트로 코딩할 수 있습니다.
리스트가 클래스보다 빠르다.
heapq module
모듈 임포트
heapq 모듈은 파이썬 내장 모듈이다.
from heapq import heappush, heappop최소 힙 생성
heapq 모듈은 파이썬의 리스트를 마치 힙처럼 다룰 수 있게 도와준다.
빈 리스트를 생성후 heapq 모듈 함수를 호출할 때마다 리스트에 인자로 넘기면된다.
heap = [] 힙에 원소 추가 및 삭제
from heapq import heappush, heappop
heap = []
heappush(heap,4)
heappush(heap,1)
heappush(heap,7)
heappush(heap,3)
print(heap)
>>>[1, 3, 7, 4]
heappop(heap)
>>> 1
print(heapq)
>>>[3,7,4]최소값 삭제하지 않고 얻기
print(heap[0])
>>> 3기존 리스트를 힙으로 변환
이미 원소가 들어있는 리스트를 힙으로 만드려면 heapyfy()라는 함수를 사용하면 된다.
from heapq import heapify
heap = [4,1,7,3,2,6]
heapify(heap)
print(heap)
>>> [1, 2, 6, 4, 3, 7]heapify() 함수의 성능은 인자로 넘기는 리스트의 원소수에 비례한다. 즉 O(n)의 시간복잡도를 가집니다.
heapify() 함수에서 주의할 점은 새로운 리스트를 반환하는 것이 아니라 인자로 넘긴 리스트에 직접 변경한다는 것입니다. 따라서 원본 리스트의 형태를 보존해야되는 경우에는 반드시 해당 리스트를 복제한 후에 인자로 넘겨야 하겠습니다.
heapq 모듈들 응용방법
최대 힙
import heapq
n = [4, 1, 7, 3, 8, 5]
heap = []
for num in nums:
heapq.heappush(heap, (-n, n))
while heap:
print(heapq.heappop(heap)[1])
>>>8
>>>7
>>>5
>>>4
>>>3
>>>1힙에 원소를 추가할때 (-원소의 값,원소의 값)으로 저장을 해준다면
음수의 값으로 최소 힙이 되므로 그 뜻은 원래 양수의 값에서 최대 힙이 된다는 뜻이다.
이런 식으로 조금 응용을 한다면 최대 힙을 구할 수 있다.
n번째 최소값
heapq 모듈에 nsmallest()라는 함수가 존재합니다.
nsmallest() 함수는 주어진 리스트에서 가장 작은 n개의 값을 담은 리스트를 반환하는데, 그 결과 리스트의 마지막 값이 n 번째 작은 값이 되겠습니다.
import heapq
n = 2
q = []
for _ in range(n):
for i in map(int,input().split()):
heapq.heappush(q,i)
q = heapq.nsmallest(n,q)
print(q)
>>> [1,3]힙 정렬
힙 정렬은 위에 설명한 힙 자료구조의 성질을 이용한 대표적인 정렬 알고리즘이다.
장점
- 시간 복잡도가 좋은편이다.
- 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때 힙 정렬이 가장 유용하다.
시간 복잡도
- 힙 트리의 전체 높이가 거의 log2n (완전 이진 트리)이므로 하나의 요소를 힙에 삽입하거나 삭제할 때 힙을 재정비하는 시간이 log2n만큼 소요된다.
- 요소의 개수가 n개 이므로 전체적으로 O(nlog2n)의 시간이 걸린다.
- T(n) = ** O(nlog2n)
import heapq
def heap_sort(nums):
heapq.heapify(nums)
sorted_nums = []
while nums:
sorted_nums.append(heapq.heappop(nums))
return sorted_nums
print(heap_sort([4, 1, 7, 3, 8, 5]))출처
https://www.daleseo.com/python-heapq/
https://asfirstalways.tistory.com/325
https://zu-techlog.tistory.com/31
https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html
