파이썬에서 힙(heap) 사용하기 - heapq

이번 블로그는 파이썬을 이용해서 힙 자료구조를 이용하는 방법을 정리해보고자 한다.

일단 힙(heap)은 우선순위 큐를 만들때 이용하면 좋다.

---

[자료구조]

먼저 알아야한 자료구조들에 대해서 간단하게 정리해보자!

- 스택(LIFO : Last In First Out)

: 자료가 들어오는 순서대로 위로 쌓인다고 생각하면 됨

- 큐(FIFO : First In First Out)

: 자료가 들어오는 순서대로 영화관 줄 처럼 줄을 서 있는다고 생각하면 됨. 

- 우선순위 큐(Priority Queue)

: 들어온 순서에 상관없이 우선순위에 따라 데이터가 처리되는 자료구조.

: 힙(heap)자료구조로 구현할 수 있다.

이 중에서 우선순위 큐(Priority Queue)가 힙 자료구조에 이용된다.

우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하다. 이중에서 힙(heap)으로 구현하는 것이 가장 효율적이다.

---

파이썬에서 힙(heap)자료구조 사용하기 - heapq

 

이번 블로그에서는 힙에서 삭제, 삽입이 어떻게 구현되는지 자세한 매커니즘에 대해서는 다루지 않고 

파이썬에 이미 구현되어있는 heapq라는 모듈이 무엇이고 어떻게 사용할 수 있는지 다뤄보겠다.

 

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

다시말해서 heapq를 이용하면 따로 정렬할 필요 없이 최소값이 가장 먼저 처리될 수 있는 자료구조를 만들어준다는 것이다.

 

모듈 임포트

파이썬에서는 내장모듈로 heapq를 제공하고 있기 때문에 따로 설치할 필요 없이 import heapq만 해주면 사용할 수 있다.

import heapq

최소 힙 생성

heaqp 모듈은 파이썬의 리스트를 최소 힙처럼 다룰 수 있게 해준다.

그렇기 때문에 빈 리스트를 따로 만들어주고 heapq.heappush 또는 heapq.heappop을 이용해서 원소를 추가 삭제해주면 된다.

heap = []

힙(heap)에 원소 추가 - heappush()

heappush()의 첫번째 인자는 원소를 추가할 대상이 되는 리스트이다. 아까 위에서 만든 빈 리스트 heap을 넣어주면 된다.

두번째 인자에는 추가할 원소를 넣어준다.

heapq.heappush(heap,1)
heapq.heappush(heap,3)
heapq.heappush(heap,5)
heapq.heappush(heap,2)

prınt(heap) # [1, 2, 3, 5]

추가되는 순서와 상관없이 가장 작은 값이 첫번째로 위치하는 것을 확인할 수 있다.

heappush()함수는 내부적으로 이진트리구조에서 원소를 추가하는 방법으로 구현되기 떄문에 O(logN)의 시간복잡도를 갖는다.

 

힙(heap)에서 원소 삭제 - heappop()

heappush()의 첫번째 인자는 원소를 석제할 대상이 되는 리스트이다. 여기도 똑같이 아까 위에서 만든 빈 리스트 heap을 넣어주면 된다.

두번째 인자에는 삭제할 원소를 넣어준다.

print(heapq.heappop(heap)) # 1
print(heap) # [2, 3, 5]

print(heapq.heappop(heap)) # 2
print(heap) # [3, 5]

heappop()은 힙 내에서 가장 최소값을 삭제해낸다.

다시한번 파이썬 heapq는 기본적으로 최소힙을 만들어준다는 것을 까먹지 말자!

 

힙(heap)에서 원소 값 얻기

힙에서 원소값을 얻는 방법은 리스트에서 인덱싱하는 방법과 동일하다.

print(heap[0]) # 3

여기에서 주의할 점은 0번째 인덱스에는 최소값이 있지만 1번째 인덱스나 2번째 인덱스에 순서대로 최소값이 있다는 보장은 없다. 왜냐하면 heap은 이진트리구조를 기반으로 하고 있기 때문이다.

따라서 두번째로 작은 원소를 얻고 싶다면 heappop()을 통해서 가장 작은 원소를 빼내고 난 후 한번더 heap[0]을 통해서 원하는 원소를 얻어야 한다.

 

리스트를 힙으로 전환 - heapify

heapify()함수를 이용하면 리스트를 힙으로 전환시켜준다.

heap = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap)

print(heap) # [1, 3, 5, 4, 8, 7]

heapify()에 리스트를 인자로 넘겨주면 리스트를 최소힙으로 바꿔준다.

heapify()함수는 O(N)의 시간복잡도를 갖는다.

 

최대 힙 만들기

그렇다면 최대힙(max heap)은 어떻게 만들수 있을까? heapq은 최소힙(min heap)만을 만들어주기 때문에 약간의 스킬만 이용하면 최대 힙을 만들 수 있따.

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
  heapq.heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
  print(heapq.heappop(heap)[1])  # index 1
  
8
7
5
4
3
1

튜플내에서는 첫번째 것을 기준으로 우선순위를 따진다는 것을 이용해서

튜플의 첫번쨰 값으로 부호를 바꾼 값을 넣어주고 튜플의 두번째 값을 넣거나 빼면 자동으로 최대힙을 이용할 수 있다.