[python] Heapq 힙 모듈?! (heapq의 사용법)

힙(Heap) 은 그래프랑 트리와는 전혀 상관없는 이름을 가지고 있다..

 

하지만 힙은 트리 기반의 자료구조이다.

 

모듈은 주로 heapq를 사용하며 파이썬에는 최소 힙만 구현되어 있다.

 

최소 힙이란 부모가 항상 자식보다 작기 때문에 루트가 결국 가장 작은 값을 갖는 형태다.

 

그러면 파이썬은 최소 힙이니 정렬이 되어 있어야 할까??

 

아니다..! 부모가 가장 작다는 것만 만족하면 될 뿐 정렬이 되어 있을 필요는 없다.

 

BST(이진 탐색 트리)랑 다른 점은 BST는 정렬이 되어있어 최상단 노드 왼쪽에는 최상단 노드보다 작은 값이 오고, 최상단 노드 오른쪽에는 최상단 노드보다 크거나 같은 값이 온다.

 

왼쪽인 최소힙이고 오른쪽이 BST의 예시이다.

 

최상단 노드를 기준으로 정렬의 차이가 보인다.

 

 

Heapq 사용하기

 

우선 heapq 사용하기 위해서는 import부터 해줘야 한다.

 

import heapq

 

heapq는 내장 모듈이기 때문에 파이썬이 설치되어 있다면 사용이 가능하다.

 

Heapq 생성하기

heap = []

 

Heapq는 리스트를 최소 힙처럼 다룰 수 있도록 도와주기 때문에 리스트를 가지고 활용하면 된다.

 

 

 Heapq 원소 추가(push)

heap_list = []
heapq.heappush(heap_list, 1)

 

위와 같은 식으로 리스트에 원소를 추가할 수 있다. heap자리에 리스트명이 들어가면 된다.

 

Heapq 원소 최솟값 얻기

최솟값을 얻는 방법에는 두 가지 방법이 존재한다.

 

Heapq 인덱스로 최솟값 얻기

heap_list = [3, 2, 1]
heapq.heapify(heap_list) #heapq.heapify(list)를 통하여 list를 최소힙으로 만들수 있다.
print(heap_list[0])

 

1

 

리스트를 heapq를 통하여 최소 힙으로 만들면 인덱스 0번에 최솟값(최상단 노드)이 위치하게 된다.

 

 

Heapq pop으로 최솟값 얻기

heap_list = [3, 2, 1]
heapq.heapify(heap_list) #heapq.heapify(list)를 통하여 list를 최소힙으로 만들수 있다.
print(heapq.heappop(heap_list))
print(heap_list)

 

1
[2, 3]

 

heappop(list명)을 통하여 list에서 값을 추출할 수 있다. 가장 최솟값이 나오게 된다. 

 

또한 pop이기 때문에 1이 리스트에서 없어진 것을 확인할 수 있다.

 

 

List to Heap (리스트를 힙으로 변환)

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

 

[1, 2, 3]

 

최솟값 얻을 때 사용했듯이 heapq.heapify(list)를 통하여 list를 최소 힙으로 만들수 있다. 

 

list를 출력하면 최소힙 형태로 바뀐 것을 확인할 수 있다.

 

 

최대 힙으로 만들기

키 값을 변환해서 넣는다면 최대힙으로 만들 수도 있다.

모든 요소의 키를 바꾸는데 드는 시간은 O(n)이고, 모든 힙 요소를 얻는데 드는 시간은 O(nlogn)이다.

 

 

 

 

힙 관련 문제

[프로그래머스] 더 맵게

TISTORY