힙 / 힙큐(heapq)

힙

특정한 규칙을 가지는 완전 이진 트리로 최댓값과 최솟값을 찿는 연산을 빠르게 하기 위한 자료구조이다.

 

A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립

최소 힙 : 부모 노드의 키값이 자식 노드의 키 값보다 항상 작은 힙

최대 힙 : 부모 노드의 키값이 자식 노드의 키 값보다 항상 큰 힙

 

파이썬에서는 heapq를 제공한다.

모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리 구조인데, 내부적으로는 인덱스 0에서 시작해 k번째 원소가 항상 자식 원소들(2k+1, 2k+2)보다 작거나 같은 최소 힙의 형태로 정렬된다.

 

import heapq

heapq.heappush(heap,item) # item을 heap에 추가
heapq.heappop(heap) # heap에서 가장 작은 원소를 pop & 리턴, 비어 있는 경우 IndexError가 호출
heapq.heapify(x) # 리스트 x를 heap으로 변환 O(N)
heapq[0] # 최소값 삭제하지 않고 얻기

 

* 최대 힙

파이썬의 heapq 모듈은 최소 힙으로 구현되어 있기 때문에 최대 힙 구현을 위해서는 약간의 변화가 필요하다.

 

y = -x 변환을 하면 최솟값 정렬이 최댓값 정렬로 바뀐다.

import heapq

heap_items = [1,3,5,7,9]

num = [1,3,5,7,9]
heap = []

for i in num:
    heapq.heappush(heap,(-i,i))

print(heap)
# [(-9, 9), (-7, 7), (-3, 3), (-1, 1), (-5, 5)]


while heap:
    print(heapq.heappop(heap)[1])
  
9
7
5
3
1