[Python] heapq 모듈

heap

 

• 힙은 최댓값과 최솟값을 빠르게 찾아내기 위한 자료구조
• 우선순위 큐를 구현하기 위한 자료형
• heap은 list 기반으로 동작
• heap의 root가 가장 작은 값을 가지는 최소힙

 

heapq

• Python에서는 heap 자료구조를 쉽게 구현할 수 있도록 도와주는 내장 heapq 모듈이 존재한다

import heapq

 

heapq.heappush()

• heapq.heappush( heap으로 사용될 list, 넣고자 하는 값 )
  • 첫 번째 인수는 heap으로 사용될 list가 들어가고 두 번째 인수로는 넣고자 하는 값이 들어간다.
• heap에 값을 삽입

import heapq

heap = []

# heap.heappush(list, item)
heapq.heappush(heap, 3)
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)

print(heap) 

#결과
[1, 4, 3]

 

 

heapq.heappop()

• 힙에서 root 값 출력후 삭제 (최솟값 리턴)
• → pop후에 남은 값들 정렬됨

import heapq
...

# heap.heappop(list)
print(heapq.heappop(heap))
print(heap)

#결과
1
[3,4]

 

 

heapq.heapify()

• 이미 주어진 list를 heap으로 만들 때는 heapify 메서드를 활용

import heapq

heap = [9, 8, 7, 6, 5, 4, 3, 2, 1]

# heapq.heapify(list)
heapq.heapify(heap)

print(heap) 

#결과
[1, 2, 3, 6, 5, 4, 7, 8, 9]

 

heapq.nlargest() / heapq.nsmallest()

• heapq.nlargest( n, list )
  • 가장 큰 값부터 n개 리스트로 출력 
• heapq.nsmallest( n, list )
  • 가장 작은 값 부터 n개 리스트로 출력

import heapq
...

print(heapq.nsmallest(3, heap)) 
print(heapq.nlargest(3, heap)) 
 
#결과
[1, 2, 3]
[9, 8, 7]

 

최대 힙 만들기

# 최대 힙 만들기
import heapq

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

for num in nums:
	#(우선순위, 값)을 튜플 형태로 힙에 저장	
    heapq.heappush(heap, (-num, num)) 
    
while heap:
	# 값만 print
    print(heapq.heappop(heap)[1])

 

• heapq.heappush( heap , value ) 
  • 값이 삽입된 후에 최소힙 구조가 됨
• heapq.heappop( heap )
  • -> 최소힙의 루트가 반환되는 것

 

---

출처
https://buyandpray.tistory.com/30
https://velog.io/@t1won/Python-heapq