[python] heapq모듈

📒 기본적인 사용법

#min heap(최소 힙)에서 가장 작은값은 언제나 인덱스 0, 즉, 이진 트리의 루트에 위치
#      1  ---> root
#    /   \
#   3     5
#  / \   /
# 4   8 7

#heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공
#heqpq모듈은 파이썬의 보통 리스트를 마치 최소 힙처럼 다룰 수 있도록 도와줌. 별개의 자료구조 X
#파이썬에서는 heapq 모듈을 통해서 원소를 추가하거나 삭제한 리스트가 그냥 최소 힙이 됨.

import heapq

a = [] #파이썬의 일반적인 리스트 선언

heapq.heappush(a, 6)   #리스트를 인자로 넘겨 원소를 추가
heapq.heappush(a, 1)
heapq.heappush(a, 4)
heapq.heappush(a, 5)

print(a)  #[1, 5, 4, 6]

print(heapq.heappop(a)) #리스트를 인자로 넘겨 원소를 삭제. 1 출력 됨.
print(heapq.heappop(a)) #4 출력
print(a[0])  #제거하지 않고 최소값 5출력, 그 전에 heapq모듈의 함수를 사용했기 때문에 가장 작은 값이 0인덱스에 오도록 정렬되어 있음.
print(a)  #[5, 6]

#----------------------------------------------------#
#heapq.heappop() 주의할 점
#제일 앞에 있는 원소 제거하고 힙 구조로 만듬
c = [6, 8, 4, 1] 

print(c) #[6, 8, 4, 1]
print(heapq.heappop(c))  #6
print(c)  #[1, 8, 4]
print(heapq.heappop(c))   #1
print(c)  #[4, 8]
print(heapq.heappop(c))  #4
print(c)   #[8]
print(heapq.heappop(c))  #8
#----------------------------------------------------#

#힙 구조로 재배치
b = [4, 1, 7, 3, 8, 5]
heapq.heapify(b)   #힙 구조에 맞게 b가 재배치 됨
print(b)

📒 응용

#최대 힙 -------------------------------------------

import heapq

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

for num in nums:
    heapq.heappush(max_heap, (-num, num))

while max_heap:
    print(heapq.heappop(max_heap)[1])   # 출력
                                        # 8
                                        # 7
                                        # 5
                                        # 4
                                        # 3
                                        # 1  
                                        
# K번째 최소값 ------------------------------------------

def k_min_val(list, k):

    heapq.heapify(list)  #최소 힙 구조로 재배치
    
    for _ in range(k):   #heappop을 k번 반복
        min = heapq.heappop(list)

    return min

a = [8,3,7,5,6]
print(k_min_val(a, 3))   #6출력


#힙 정렬 ------------------------------------------------

def sort_heap(list):

    nums = []
    for i in list:   # 이 부분 heapq.heapify()로 대체 가능
        heapq.heappush(nums, i)      
    
    sorted_nums = []
    while nums:
        sorted_nums.append(heapq.heappop(nums))

    return sorted_nums

b = [8,3,7,5,6]
print(sort_heap(b))   #[3, 5, 6, 7, 8]