-
heapq파이썬 Study/라이브러리 2021. 3. 11. 22:08
■ heapq
- 파이썬에서는 이진트리 기반의 min 정렬 heap library 제공
1) 정의 :
이진트리 기반 min heap → 최상위 root node가 min 값
2) 예시 :
- 별도의 heap list를 선언하고, 함수를 이용해서 sort하는 방식
- 반드시 heapq 모듈을 통해서 작업을 해야 min heap으로 정렬됨
(a) 원소 추가
import heapq heap = [] heapq.heappush(heap, 4) heapq.heappush(heap, 1) heapq.heappush(heap, 7) heapq.heappush(heap, 3) print(heap) >>> [1, 3, 7, 4]
(b) 원소 제거
# heap = [1, 3, 7, 4] print(heapq.heappop(heap)) >>> 1 print(heap) >>> [3, 4, 7]
(c) 최소값 읽기 (w/o deletion)
- 최소값을 삭제하지 않고 단순히 읽기만 하려면 일반적으로 리스트의 첫번째 원소에 접근하듯이
인덱스를 통해 접근
# heap = [1, 3, 7, 4] print(heap[0]) >>> 1
(d) heapify
- 기존 전체 list를 min heap로 반환
- O(N)의 시간복잡도
heap = [4, 1, 7, 3, 8, 5] heapq.heapify(heap) print(heap) >>> [1, 3, 5, 4, 8, 7]
(e) max heap 구현 방법
- 새 list 선언 이후, 원소를 tuple로 배치
- tuple은 (우선순위, 값)의 인자로 인식됨, 함수 내부에서
import heapq nums = [4, 1, 7, 3, 8, 5] heap = [] for num in nums: heapq.heappush(heap, (-num, num)) # (우선 순위, 값) while heap: print(heapq.heappop(heap)[1]) # index 1 >>> 8 7 5 4 3 1
(f) k 번째 최소 / 최대 값 구하기
- k번째 최소
import heapq def kth_smallest(nums, k): heap = [] for num in nums: heapq.heappush(heap, num) kth_min = None for _ in range(k): kth_min = heapq.heappop(heap) return kth_min print(kth_smallest([4, 1, 7, 3, 8, 5], 3)) >>> 4
- k번째 최소
import heapq def kth_maxest(nums, k): heap = [] for num in nums: heapq.heappush(heap, (-num, num) ) kth_max = None for i in range(k): kth_max = heapq.heappop(heap) return kth_max print(kth_maxest([4, 1, 7, 3, 8, 5], 3)) >>> 5
출처:
https://www.daleseo.com/python-heapq/
[파이썬] heapq 모듈 사용법
Engineering Blog by Dale Seo
www.daleseo.com
https://velog.io/@sossont/Python-heapq-%EB%AA%A8%EB%93%88
[Python] heapq 모듈
heapq 모듈은 이진 트리 기반의 최소 힙(min heap) 자료구조를 제공합니다. 자바의 PriorityQueue 클래스와 비슷하다고 생각하시면 될 듯 합니다.min heap에서 가장 작은 값은 언제나 0번 인덱스(이진 트리
velog.io
반응형'파이썬 Study > 라이브러리' 카테고리의 다른 글
hashing (1) 2021.03.11 collections - defaultdict (1) 2021.03.11 queue (1) 2021.03.11 list - instance (1) 2021.03.11 sorted 발전 - 수정 (1) 2021.03.11