[파이썬] 힙(Heap) - heapq 모듈 ( import heapq )

힙 자료구조

• 데이터를 정렬된 상태로 저장하기 위해서 사용하는 파이썬 heapq(힙큐) 내장 모듈 사용
• heapq 모듈은 이진트리(binart tree)기반의 최소 힙(min heap) 자료구조를 제공한다
• 최대, 최소값을 가져올 때 많이 사용한다

 

힙 관련 함수들 (import heapq)

• 힙 생성 - heap = [] 
• 힙 원소 추가 - heapq.heappush(heap, 4)
• 힙에서 원소 삭제 heapq.heappop(heap)) // 가장 작은 원소 삭제 후 그 값 리턴
• 최솟값 삭제하지 않고 얻기 - heap[0]
• 기존 리스트를 힙으로 변환 - heapq.heapify(heap)

import heapq	# 모듈 임포트
heap = []		# 힙 생성

# 힙에 원소 추가
heapq.heappush(heap, 4)	
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap)
>>> [1, 3, 7, 4]

# 힙에서 원소 삭제
print(heapq.heappop(heap))	# 가장 작은 원소 삭제 후 그 값 리턴
print(heap)	
>>> 1
>>> [3, 4, 7]

# 최소값 삭제하지 않고 얻기
print(heap[0])
>>> 3

# 기존 리스트를 힙으로 변환
heap = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap)
print(heap)
>>> [1, 3, 5, 4, 8, 7]

 

+ 힙 정렬

import heapq

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

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

>>> [1, 3, 4, 5, 7, 8]

 

+ 최대 힙

• heapq 모듈은 최소 힙만 동작하기 때문에 최대 힙으로 하기 위해 요령이 필요
• 힙에 튜플(tuple)을 원소로 추가하거나 삭제하면, 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리를 이용한다
• 따라서, 최대 힙을 만들려면 각 값에 대한 우선순위를 구한 후, (우선 순위, 값) 구조의 튜플(tuple)을 힙에 추가하거나 삭제하면 됩니다. 그리고 힙에서 값을 읽어올 때는 각 튜플에서 인덱스 1에 있는 값을 취하면 됩니다. (우선순위에는 관심이 없으므로 )

import heapq

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

for num in nums:
  heapq.heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
  print(heapq.heappop(heap)[1])  # index 1
  
>>> 8
>>> 7
>>> 5
>>> 4
>>> 3
>>> 1

 

+ K번째 최소값/최대값

• K번째 최소값을 구하기 위해서는 주어진 배열로 힙을 만든 후, heappop() 함수를 K번 호출하면 됩니다.

import heapq

def kth_smallest(nums, k):
  heap = []
  for num in nums:
    heapq.heappush(heap, num)

  kth_min = None
  for _ in range(k):
    kth_min = heapq.heappop(heap)
  return kth_min

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

>>> 4

 

+ 힙 개념 문제 :

2021.03.19 - [알고리즘] - 20210319_코테공부

20210319_코테공부

 

+ 이중우선순위큐

https://programmers.co.kr/learn/courses/30/lessons/42628

코딩테스트 연습 - 이중우선순위큐