[Algorithm] 힙 | 최대 힙, 최소 힙

heap이란?

: 우선 순위 큐(priority queue)를 구현하기 위해 사용하는 자료구조 중 하나로, 완전이진트리를 base로 한 자료구조.

• 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 점이 특징
• 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙
• 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙

 

자료구조	추출되는 데이터
스택(stack)	가장 나중에 삽입된 데이터
큐(queue)	가장 먼저 삽입된 데이터
우선순위 큐(priority queue)	가장 우선 순위가 높은 데이터

 

최소 힙 (min heap)

: 값이 가장 낮은 데이터가 먼저 삭제

import heapq 

heap = [] 

heapq.heappush(heap, 5) 
heapq.heappush(heap, 1) 
heapq.heappush(heap, 2) 

print(heap) # [1, 5, 2] 
print(heapq.heappop(heap)) # 1

 

최대 힙 (max heap)

: 값이 큰 데이터가 가장 먼저 삭제

• Python에서 힙 라이브러리를 사용 시에는 default 값이 최소 힙으로 되어있으므로, 최대 힙으로 사용 시에는, 값에 음수 부호(-)를 붙여서 넣었다가, 값을 추출 시에 다시 음수 부호(-)를 붙여 원래의 값으로 되돌린다.

import heapq

heap = [] # 현재: 5, 1, 2를 최대 힙에 넣고 싶은 상태.
heapq.heappush(heap, -5)
heapq.heappush(heap, -1)
heapq.heappush(heap, -2)

print(heap) # [-5, -1, -2]
print(-heapq.heappop(heap)) # 5