[Python] 힙 라이브러리 (heapq)

최소힙

import heapq

min_heap = [6, 1, 8, 5, 4, 3, 7]

# 힙 변환 
# 시간복잡도 O(N)
heapq.heapify(min_heap)     #[1, 4, 3, 5, 6, 8, 7]

# root(최소값) 반환, 비어 있는 경우 IndexError
# 시간복잡도 O(logN)
heapq.heappop(min_heap)     #[3, 4, 7, 5, 6, 8]

# 힙에 원소 추가
heapq.heappush(min_heap, 2)     #[2, 4, 3, 5, 6, 8, 7]

 

힙 (heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된
완전이진트리(complete binary tree)

부모노드와 자식노드 간에만 대소관계가 성립되지만,
형제 사이는 상관없다.

부모노드의 순서가 i일때,
left는 2*i + 1 , right는 2 * i +2이기 때문에
리스트로 구현 가능.

높이는 log(N)

최대힙

import heapq

max_heap = [6, 3, 9, 2, 4, 7]


# 최소힙 응용 1 (-1 곱하기)
max_heap1 = [i * -1 for i im max_heap]
heapq.heapify(max_heap1)
wight = heapq.heappop(max_heap1)
value = -1 * weight


# 최소힙 응용 2
max_heap2 = [(-1 * i, i) for i in max_heap]
heapq.heapify(max_heap2)
weight, value = heapq.heappop(max_heap2)


# 최대힙 함수
heapq.heapify_max(max_heap)
value = heapq._heappop_max(max_heap)