heapq, 우선순위 큐

- 모듈 import

from heapq import heappush, heappop

- 최소 힙 생성

빈 리스트를 생성 후 heapq 모듈의 함수를 호출할 때 이 리스트를 인자로 넘겨줌

heap = []

- 힙에 원소 추가

from heapq import heappush, heappop

heap = []
heappush(heap, 4)
heappush(heap, 1)
heappush(heap, 7)
heappush(heap, 3)

heap = [1, 3, 7, 4]

• 가장 작은 1이 인덱스의 0번에 위치하며, heappush 함수는 O(log(n))의 시간복잡도

- 힙에서 원소 삭제

from heapq import heappop

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

• heappop(heap) 원소를 삭제할 리스트를 넘기면, 가장 작은 원소 삭제 후 그 값을 리턴
• 삭제하지 않고 최소값을 얻으려면 print(heap[0])
  • 인덱스0에 가장 작은 원소가 있다고 해서, 1에 두번째 작은 원소, 2에 세번째 작은 원소 있다는 보장X
  • heappop() 사용할 때 마다 이진 트리 재배치 통하여 매번 새로운 최소값을 인덱스 0에 저장하는 구조

- 기존 리스트를 힙으로 변환

from heapq import heapify

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

• heapify() 함수에 리스트를 인자로 넘기면, 내부의 원소들이 힙 구조에 맞게 재배치

• 새로운 리스트 반환이 아니라, 해당 리스트를 직접 변경

  from heapq import heapify
  
  nums = [4, 1, 7, 3, 8, 5]
  heap = nums[:]
  
  print(nums)		# [4, 1, 7, 3, 8, 5]
  print(heap)		# [1, 3, 5, 4, 8, 7]

- 최대 힙

from heapq import heappush, heappop

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

for num in nums:
    heappush(heap, (-num, num))		# (우선 순위, 값)
    
while heap:
    print(heappop(heap)[1])		# 8, 7, 5, 4, 3, 1

• 각 값에 대한 우선 순위를 구한 후, (우선순위, 값) 구조의 튜플을 힙에 추가하거나 삭제
• 힙에서 값을 읽어올 때는 각 튜플에서 인덱스 1에 있는 값을 취하면 됨

- n번째 최소값 / 최대값

from heapq import heappush, heappop

def nth_smallest(nums, n):
    heap = []
    for num in nums:
        heappush(heap, num)
        
    nth_min = None
    for _ in ragne(n):
        nth_min = heappop(heap)
        
    return ntn_min

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

• n번째 작은 값이나 n번째로 큰 값을 효과적으로 구할 수 있음

• 주어진 배열로 힙을 만든 후, heappop() 함수를 n번 호출

• heapify() 함수 사용

  from heapq import heapify, heappop
  
  def nth_smallest(nums, n):
      heapify(nums)
  
      nth_min = None
      for _ in range(n):
          nth_min = heappop(nums)
  
      return nth_min

• nsmallest() 함수 사용

  from heapq import nsmallest
  
  nsmallest(3, [4, 1, 7, 3, 8, 5])[-1]

  • 주어진 리스트에서 가장 작은 n개의 값을 담은 리스트 반환

    → 리스트의 마지막 값이 n 번째 작은 값

• nlargest() 함수 사용

  from heapq import nlargest
  
  nlargest(3, [4, 1, 7, 3, 8, 5])[-1]

- 힙 정렬

from heapq import heappush, heappop

def heap_sort(nums):
    heap = []
    for num in nums:
        heappush(heap, num)
        
    sorted_nums = []
    while heap:
        sorted_nums.append(heappop(heap))
    return sorted_nums

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