python heapq

설명

 

heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조

python에서 제공하는 heapq는 min-heap (최소힙)을 기본으로 제공한다.

    ex) [70,50,80,50] -> [50,50,80,70]이 된다.

알고리즘 문제를 풀다보면 단순 List의 append, pop을 사용하다가 시간초과(효율성검사)되는 경우가 발생..
그럴때, heapq를 쓰면 시간복잡도가 나아지는지 효율성검사 통과하게됨.

 

---

 

사용법

 

선언

import heapq

 

List -> heap 변경

import heapq

a = [1,2,3]
heapq.heapify(a)

 

heap push, pop

import heapq

heapq.heappush(1,a) # push 1 , [1,2,3] -> [1,1,2,3]
heapq.heappop(a) # pop [1,1,2,3] -> [1,2,3]

 

---

 

heapq가 기존 list append, pop 보다 왜 속도면에서 빠른지 궁금했다.
heapq에 대해 세부적인 동작방식이 궁금하다면 아래 링크를 보면 heapq.py source code를 볼 수 있다.
Click