[Python] heapq

Heap

파이썬의 heapq 모듈에 대해 알아보기 전에 먼저 힙이 무엇인지 알아야 할 것 같다. 힙 자료구조는 완전 이진 트리를 기초로 하는 자료구조이며, 완전 이진트리란 마지막을 제외한 모든 노드에서 자식들이 꽉 채워진 이진트리를 말한다. 그래서 이를 이용한 힙 정렬은 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로, 시간복잡도는 O(NlogN)으로 빠른 정렬에 속한다.

 

• 최소 힙(Min Heap) : 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
• 최대 힙(Max Heap) : 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

 

heapq

파이썬에서는 heapq 모듈을 통해 힙을 쉽게 표현할 수 있다. 내장 모듈로써 따로 설치없이 바로 사용가능하며, 리스트를 최소 힙의 형태로 정렬해준다.

import heapq

heap = []
l = [10, 1, 5]

heapq.heappush(heap, 10)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)
print(heap)			# [1, 10, 5]

heapq.heappop(heap) 		# heap에서 가장 작은 원소를 꺼내고 리턴, 비어 있는 경우 IndexError
print(heap)			# [5, 10]

heapq.heapify(l)		# 리스트를 힙으로 변환
print(l)			# [1, 10, 5]