[Python] 최소힙(MIN heap) / 최대힙(MAX heap)

 

 

힙은 자료구조 트리를 사용하여 구현한다. 트리 중에서도 완전 이진트리이다. 

최대 트리는 항상 부모가 자식보다 값이 크다.

최소 트리는 항상 부모가 자식보다 값이 작다.

 

 

(자식끼리는 상관X)

python으로 어떻게 구현할 것인가? 고민할 필요 없이 module을 쓰도록 하겠다.

 

최소(Min) heap

python은 기본적으로 최소 heap을 구현할 수 있는 모듈을 제공한다.

import heapq

 

heap으로 선언하는 것은 아니고, 일반적인 배열을 heap으로 만들 수 있다.

예를 들어 정렬되지 않은 arr 배열을 heapify로 정렬할 수 있다.

heapify(정렬할리스트)

import heapq

arr = [1,5,3,6,2]

heapq.heapify(arr)
print(arr) # [1,2,3,6,5]

자식끼리는 값을비교하지 않으므로 sort와는 결과적으로 차이가 있다.

 

값을 넣는 순간부터 heap정렬을 하고 싶다면 아래와 같이 구현하면 된다.

heappush(정렬할리스트, 정렬할값)

import heapq

arr = []

for i in range(10, 0, -1):
    heapq.heappush(arr, i)

print(arr) # [1, 2, 5, 4, 3, 9, 6, 10, 7, 8]

 

값을 제거할 때는 heappop을 사용한다. 가장 작은 값(root)가 pop된다.

heappop(정렬할리스트)

import heapq

arr = [1,5,3,6,2]

heapq.heapify(arr)
pop = heapq.heappop(arr)
print(pop) # 1

 

 

최대(MAX) heap

python의 heapq은 기본적으로 최소힙만을 제공한다.

그래서 최대힙을 사용하기 위해서는 우회적으로 이용해야한다.
다양한 방법이 있지만, 내가 주로 사용하는 방법은 값에 -(마이너스)를 붙여 heap에 저장하는 방법이다.

import heapq

arr = []

for i in range(10, 0, -1):
    heapq.heappush(arr, -i)

print(arr) # [-10, -9, -8, -7, -6, -5, -4, -3, -2, -1]

마이너스를 제외하고 보면 최대힙으로 저장되어 있다.

 

값을 사용할 때는 pop 할 때 다시 마이너스를 붙이면 된다.

import heapq

arr = []

for i in range(10, 0, -1):
    heapq.heappush(arr, -i)

print(arr) # [-10, -9, -8, -7, -6, -5, -4, -3, -2, -1]

temp = heapq.heappop(arr) * -1
temp2 = -(heapq.heappop(arr))

print(temp) # 10
print(temp2) # 9

 

 

 

백준문제

📌 최소힙

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

solution

https://github.com/sladuf/Algorithm/blob/master/BaekJoon/BJ1927.py

GitHub - sladuf/Algorithm

 

 

📌 최대힙

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

solution

https://github.com/sladuf/Algorithm/blob/master/BaekJoon/BJ11279.py

GitHub - sladuf/Algorithm