[파이썬] heapq 모듈 < import heapq >

[Heapq 모듈]

- heapq

heap 같은 경우는 해당 리스트에서 가장 큰 값을 뺄 때 시간 복잡도 및 효율성을 고려한 모듈이라 할 수 있다. 데이터를 저장 후 정렬하는 것이 아니라, 데이터를 저장하면서 정렬하기 위해선 이 heapq 모듈을 사용해야 한다. 하지만 중요한 점은 heap은 이진트리를 기반으로 정렬된다는 것이다. 즉, heap으로 정렬된 리스트는 엄밀히 말하면 완전히 정렬 되진 않는다. 자식노드가 부모노드보다 크기만 하면 되는 조건을 가지고 있기에 sorted함수 와는 다르게 정렬이 된다. 그래서 heap같은 경우 최대값과 최솟값을 구할 때 주로 사용된다. (또한, heap은 root가 최솟값이 되도록 설정 된다.) 특히나 반복적으로 리스트에 값을 집어넣거나 빼면서 최대, 최솟값을 구할 때 heap을 사용하는 것을 추천한다.

 

[heap의 method들]

H= [] heapq는 기본적으로 리스트를 준비해야됨. (해당 리스트로 이진트리를 만들며 정렬)

 

heappush(H,x) 리스트H에 값x를 집넣으며 동시에 heap정렬 실행

 

heappop(H) 리스트H의 root값(최솟값) pop과 동시에 heap정렬 실행

 

_heappop_max(H) 리스트H의 root값(최댓값) pop과 동시에 heap정렬 실행

 

heapify(H) 이미 원소가 존재한 리스트 H에 heap정렬 실행 (오름차순)

 

_heapify_max(H) 이미 원소가 존재한 리스트 H에 heap정렬 실행 (내림차순)

import heapq
H = []
heapq.heappush(H, 3)
heapq.heappush(H, -1)
heapq.heappush(H, 2)
# H -> [-1, 3, 2]

heapq.heappop(H) # -1
heapq.heappop(H) # 2
heapq.heappop(H) # 3
# H -> []

H2 = [29,3,1,-4,0,8]
heapq.heapify(H2)
# H2 -> [-4, 0, 1, 3, 29, 8]