파이썬 모듈 - heapq
힙큐
- Heapq 란,
우선순위 큐
를 의미한다.최소값 부터 오름차순 으로 이루어진 큐
힙은 모든 부모 노드가 자식보다 작거나 같은 값을 갖는 이진 트리입니다. 이 구현에서는 모든 k에 대해 heap[k] <= heap[2*k+1]과 heap[k] <= heap[2*k+2]인 배열을 사용합니다
Heapq 모듈을 사용해서 heappush
, heappop
을 이용하면 힙 불변성
을 유지하며 메소드가 실행 된다.
heappop
을 이용하면, 맨 뒤엣 값이 빠져나가는 것이 아니라,최솟값
이 힙에서 빠져나가고최솟값
을 반환한다
heappush
를 이용하면 맨 뒤에 값이 들어가는 것이 아니라, 우선순위를 지키며 순서에 맞는 위치에 들어간다.
(정렬 안정성을 보장하지는 않는다.)
heapify
리스트 를 선형시간 n 을 지키며, 제자리 힙으로 변형 시킨다.
우선순위큐를 이용해서 배열을 정렬 해보자!
>>> def heapsort(iterable):
... heap = []
... for value in iterable:
... heappush(heap, value)
... return [heapq.heappop(heap) for _ in range(len(heap))]
>>> heapsort([5, 2, 3, 4, 1])
#[1,2,3,4,5]
Author And Source
이 문제에 관하여(파이썬 모듈 - heapq), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jwisgenius/파이썬-모듈-heapq저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)