---

이 모듈은 우선순위 큐 알고리즘이라고도 하는 힙(heap) 큐 알고리즘의 구현 (최소, 최대값 추출)

import

import heapq

함수

heapify(리스트) # 일반 리스트를 힙으로 변환

heappush(리스트, 원소) # 원소추가 (시간복잡도 : O(log(n)))

heappop(리스트) #원소 추출 (시간복작도 : O(log(n)))

heapify(리스트) # 기존 리스트 힙 리스트로 변환 (시간복잡도 : O(n))

** 힙 리스트를 pop을 통해 추출하지 않고, remove등 다른 방식으로 수정시 힙리스트가 깨짐

응용

최소값 삭제하지 않고 얻기

리스트[0] // *힙으로 구현한 리스트일 경우

최대 힙

heappush(heap, (-value, value))  # -value 기준 우선순위 삽입 value로 추출 
heappop(heap)[1] # 인덱스 1값 추출

n번째 최소값/최대값

def nth_smallest(리스트, n): #n번쨰 최소값
    heapify(리스트)
    nth_min = None
    for _ in range(n):
        nth_min = heappop(리스트)
    return nth_min

공식문서

https://docs.python.org/ko/3/library/heapq.html