heapq

■ 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 모듈 사용법

https://velog.io/@sossont/Python-heapq-%EB%AA%A8%EB%93%88

[Python] heapq 모듈