[Python] 파이썬 Heapq 모듈 사용하기 / 힙(Heap) 구조

Heap 이란

Heap 이란 자료구조 형태 중 하나로서 우선순위 큐를 위해 만들어진 구조이다.
(자세한 Heap에 대해 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html 참고)
 
코딩 테스트 문제 중 최솟값 , 혹은 최댓값을 계속해서 호출해야 하는 상황인 경우 Heap 구조를 이용하여 구현하면 시간측면에서 굉장히 효율적인 구현이 가능하다.

 

---

 

import heapq

heapq 모듈을 이용하여 힙 자료구조를 사용할 수 있다. heapq 는 내장 모듈이므로 따로 설치가 필요하지 않는다.
기본적으로 Min-priority-queue 구조를 가지고 있다.

import heapq

 
기존 배열을 Heap 구조로 - heapify()
 

testheap = [1,3,2,6,8,0,6]
heapq.heapify(testheap)
print(testheap)

# print 결과값 => Heap 구조로 변했다.
[0, 3, 1, 6, 8, 2, 6]

---

Heap 에 요소 추가하기 - heappush(배열이름, 요소)
 

testheap = []
heapq.heappush(testheap, 3)
heapq.heappush(testheap, 5)
heapq.heappush(testheap, 1)
heapq.heappush(testheap, -3)
print(testheap)


# print 결과값 => 
[-3, 1, 3, 5]

---

Heap 요소를 삭제하기 - heappop(배열이름)
 

testheap = []
heapq.heappush(testheap, 3)
heapq.heappush(testheap, 5)
heapq.heappush(testheap, 1)
heapq.heappush(testheap, -3)
heapq.heappop(testheap)
heapq.heappop(testheap)
print(testheap)

# print 결과값 =>
[3, 5]

힙 요소를 1개씩 삭제할 수 있다.
요소 2개가 삭제되었다. 삭제를 해도 자동으로 힙 구조는 유지된다!

---

MaxHeap 구현하기
 
 
방법 1. - 값을 집어넣었다가 꺼낼 대도 - 꺼내기

 

a = [3,5,2,4,1]
testheap = []
for i in a:
    heapq.heappush(testheap, -i)
for i in range(5):
    print(-heapq.heappop(testheap))
 
# print 결과
5
4
3
2
1

단순히 -를 붙여주는 작업만 하더라도 충분히 maxheap 의 용도처럼 사용할 수 있다.
 

 
방법 2. 튜플 이용하기

 

a = [3,5,2,4,1]
testheap = []
for i in a:
    heapq.heappush(testheap, (-i,i))
for i in range(5):
    print(heapq.heappop(testheap)[1])
    
# print 결과 =>
5
4
3
2
1

heapq 는 튜플의 첫번째 요소를 기준으로 정렬하므로 첫번째 요소에 - 값 , 2번째 요소에 원래 값을 넣어준다.