[Python] 힙 자료구조인 heapq에 대해 알아보자!

힙의 개념

• 힙은 완전 이진트리로 구성된 자료구조이다.
• 우선순위 큐를 위해 만들어진 자료구조이다.
• 힙 자료구조로 우선순위 큐를 구현할 때 삽입 삭제 모두 O(logN) 연산을 가진다.
• 최소 힙: 부모 노드의 값이 자식노드의 값보다 항상 작은 힙
• 최대 힙: 부모 노드의 값이 자식노드의 값보다 항상 큰 힙

출처: https://guides.codepath.com/compsci/Heaps

위 사진과 같이 항상 완전 이진트리로 구성되어 최소 최대 값을 빠르게 찾아낼 수 있도록 설계되어있다. 

 

heapq 모듈

파이썬에선 heapq 모듈을 이용하여 최소 힙과 최대 힙 모두 구현할 수 있다. 

 

heapq 메서드

heappush(heap, item)

힙 불변성을 유지하면서 item 값을 heap으로 푸쉬한다.

heapq.heappop(heap)

힙 불변성을 유지하면서, heap에서 가장 작은 항목을 pop 하고 반환해 주는 메서드이다. heappop 메서드는 힙이 비어있을 때 호출되면 IndexError가 발생한다. pop 하지 않고 가장 작은 값을 접근할 때 heap[0]으로 접근 할 수 있다.

heapq.heappushpop(heap, item)

힙에 item을 푸시한 뒤, heap에서 가장 작은 항목을 pop 하고 반환한다. heappush()와 heappop()을 별도로 호출하는 것보다 효율적으로 실행한다.

heapq.nlargest(n, heap, key=None)

힙 데이터 집합에서 n개의 가장 큰 요소로 구성된 리스트를 반환한다. (최소 힙에서 가장 큰 값 출력 가능)

heapq.nsmallest(n, heap, key=None)

힙 데이터 집합에서 n개의 가장 작은 요소로 구성된 리스트를 반환한다. (key로 인자 함수를 넣지 않는 이상 사용 하지 않는 함수이다.)

 

최소 힙 구현

heap 역할을 할 리스트를 선언 한 뒤, heappush를 이용하면 자동으로 정렬 되게 된다.

import heapq

heap = []

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

print(heap)

문자를 정렬할 때는 Tuple로 만들어 0번 인덱스에 정렬 순위를 넣어주면 된다.

import heapq

heap = []

heapq.heappush(heap, (3, 'Apple'))
heapq.heappush(heap, (4,'Banana'))
heapq.heappush(heap, (2, 'Orange'))
heapq.heappush(heap, (1, 'Grape'))

for i in range(len(heap)):
    print(heapq.heappop(heap)[1])

#출력결과
#Grape
#Orange
#Apple
#Banana

 

최대 힙 구현

파이썬 heapq 모듈에서는 최대 힙을 지원하지 않는다. 따라서 부호를 음수로 push 하여 pop 할 때 다시 부호를 바꿔주면 최대 힙과 동일하게 구현할 수 있다.

import heapq

heap = []
values = [1, 10, 2, 8, 5, 7, 9]

for i in values:
    heapq.heappush(heap, i * -1)

for i in range(len(heap)):
    print(heapq.heappop(heap) * -1, end=" ")
    
 # 10 9 8 7 5 2 1

 

레퍼런스

• https://velog.io/@yyj8771/Python-heapq%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%9C-%EC%B5%9C%EC%86%8C-%ED%9E%99-%EC%B5%9C%EB%8C%80-%ED%9E%99
• https://docs.python.org/2/library/heapq.html