python - heapq 사용법

 

 

• heapq 모듈은 heap 이라는 데이터 타입이 있는 것이 아니고, List 를 heap처럼 사용하는 것
• 기본적으로 최소 힙

 

heapq의 functions

 

재구조화 - heapq.heapify(x)

• list x를 heap으로 변환

import heapq

x = [22, 10, 9, 1, 4]
heapq.heapify(x)
x	# [1, 4, 9, 10, 22]

 

삽입 - heapq.heappush(h, value)

• h은 heapify 되어있는 list
• value : 삽입할 값

heapq.heappush(x, 20)
x	# [1, 4, 9, 10, 22, 20]

 

삭제 - heapq.heappop(h)

• h은 heapify 되어있는 list

pop_value = heapq.heappop(x)
print(x)		# [4, 10, 9, 20, 22]
print(pop_value)	# 1

 

삽입 & 삭제 - heapq.heappushpop(h, value)

• push와 pop을 동시에
• push, pop 따로 하는 것보다 효율적
• push를 먼저 한 후, pop 
  (최솟값보다 작은 값을 push하면, 아무 변화 없음)

pop_value = heapq.heappushpop(x, 17)
print(x)			# [9, 10, 17, 20, 22]
print(pop_value)	# 4

pop_value = heapq.heappushpop(x, 0)	
print(x)			# [9, 10, 17, 20, 22]
print(pop_value)	# 0

 

삭제 & 삽입 - heapq.heapreplace(h, value)

• pop과 push를 동시에
• heappushpop과 다른 점은 pop을 한 뒤, push
  (최솟값보다 작은 값을 push하면, 기존의 작은 값을 pop한 뒤, 새로운 값을 push)

pop_value = heapq.heapreplace(x, 1)
print(x)		# [1, 10, 17, 20, 22]
print(pop_value)	# 9

 

힙 병합 - heapq.merge( * iterables , key = None , reverse = False ) 

• 여러 개의 정렬된 입력을 하나의 정렬된 출력으로 병합
• generator 로 반환
• key = function : 정렬 순서를 결정하는 함수

inputList = [list(range(10)),
            list(range(4, 9, 2)), 
            list(range(5, 50, 5))]

outputGen = heapq.merge(*inputList)

print(list(outputGen))		# [0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 7, 8, 8, 9, 10, 15, 20, 25, 30, 35, 40, 45]

# 정렬되지 않은 리스트를 넣을 경우

outputGen = heapq.merge([2, 0, 1, 55, 30],
                        [67, 23, 1, 30, 20])
print(list(outputGen))		# [2, 0, 1, 55, 30, 67, 23, 1, 30, 20]

 

최대n개 - heapq.nlargest( n , iterable , key = None ) 

• 가장 큰 n개 원소 반환
• sorted(iterable, key=key, reverse=True)[:n] 와 같음

x = [1, 10, 17, 20, 22]
heapq.heapify(x)

heapq.nlargest(2, x)    # [22, 20]
x       # [1, 10, 17, 20, 22]

 

최소n개 - heapq.nsmallest( n , iterable , key = None ) 

• 가장 작은 n개 원소 반환
• sorted(iterable, key=key)[:n]와 같음

x = [1, 10, 17, 20, 22]
heapq.heapify(x)

heapq.nsmallest(2, x)    # [1, 10]
x       # [1, 10, 17, 20, 22]

 

 

References

https://docs.python.org/3/library/heapq.html#priority-queue-implementation-notes

heapq — Heap queue algorithm — Python 3.10.7 documentation

https://github.com/python/cpython/blob/3.10/Lib/heapq.py

GitHub - python/cpython: The Python programming language