heapq 모듈

1. 힙heap이란?

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다. 부모 노드가 자식 노드보다 항상 크면 최대 힙, 항상 작으면 최소 힙이라고 한다. 형제 사이에는 대소관계가 정해지지 않는다.

 

2. heapq 모듈

- 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공

 

3. 사용 방법

힙 리스트를 heap, 모듈은 heapq로 import 해왔을 때,

- 원소 추가: heapq.heappush(heap, 넣고싶은것)

- 원소 삭제: heapq.heappop(heap) 가장 작은 원소 삭제 후 값 리턴

- 최소값을 삭제하지 않고 읽기: 인덱싱 ([0]) 단 두 번째로 작은 수는 heappop() 후 [0]

- 기존 리스트를 힙으로 변환: heapq.heapify(heap)

 

4. 응용

- 최대 힙

- k번째 최대/최소값 구하기

- 힙 정렬

 

5. 참고 자료

공식 문서 https://docs.python.org/3.0/library/heapq.html

힙 모듈 사용법 https://www.daleseo.com/python-heapq/

힙 정렬 https://ratsgo.github.io/data%20structure&algorithm/2017/09/27/heapsort/