Heap

Heap-hop 나는 힙스터다.

 

힙(heap)은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안되었다. 힙은 모든 부모 노드가 자식보다 작거나 같은 값을 갖는 이진트리다(최소 힙의 경우).

위의 그림과 같이 힙에는 두 가지 종류가 있다.

• 최소 힙: 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같음
• 최대 힙: 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같음

따라서 항상 루트 노드(heap[0])가 최솟값 또는 최댓값이다. 이 특성을 이용해 우선순위 큐와 같은 추상적인 자료형을 구현할 수 있다. 또한 형제 노드간에는 대소 관계가 정해지지 않는다.

 

힙을 직접 구현할 수도 있지만 파이썬에는 최소 힙 알고리즘을 제공하는 heapq 모듈이 있다. heapq 모듈은 리스트를 최소 힙처럼 다룰 수 있도록 한다.

heapq — Heap queue algorithm

위 문서에서 heapq 모듈이 제공하는 함수를 확인할 수 있다.

 

다만 heapq 모듈은 최소 힙으로 구현되어 있기 때문에 최대 힙을 사용하려면 추가적인 작업이 필요하다.

해결법은 아래와 같이 힙에 값을 넣을 때 부호를 변경해서 넣어준 후 꺼낼 때 다시 부호를 바꿔주는 것이다. 

import heapq

heap = []
values = [1,2,3,4,5]

for v in values:
	heapq.heappush(heap, -v)

for i in range(5):
	print(-heapq.heappop(heap))

위 코드를 실행하면 5,4,3,2,1이 출력된다.