오늘은 코테에 가끔씩 나오는 힙을 사용하는 문제를 대비하기 위해 heap에 대해 알아보도록 하겠습니다
📌 힙이란?
힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다.
힙 property : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립한다
최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙
이러한 속성으로 인해 힙에서는 가장 낮은(혹은 높은) 우선순위를 가지는 노드가 항상 루트에 오게 되고 이를 이용해 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.
이때 키값의 대소 관계는 부모/자식 간에만 성립하고, 형제노드 사이에는 대소 관계가 정해지지 않는다.
파이썬 힙
파이썬 heapq 모듈은 heapq (priority queue) 알고리즘을 제공한다.
모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리(binary tree) 구조인데, 내부적으로는 인덱스 0에서 시작해 k번째 원소가 항상 자식 원소들(2k+1, 2k+2) 보다 작거나 같은 최소 힙의 형태로 정렬된다.
heapq는 내장 모듈로 별도의 설치 작업 없이 바로 사용할 수 있다.
힙 활용
- heapq.heappush(heap, item) : item을 heap에 추가
- heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨.
- heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )
힙 생성 & 원소 추가
heapq 모듈은 리스트를 최소 힙처럼 다룰 수 있도록 하기 때문에, 빈 리스트를 생성한 후 heapq의 함수를 호출할 때마다 리스트를 인자에 넘겨야 한다.
아래 코드는 heap이라는 빈 리스트를 생성하고 50, 10, 20을 각각 추가하는 예시이다.
import heapq
heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)
print(heap)
-------
output
[10, 50 ,20 ]이미 생성해둔 리스트가 있다면 heapify 함수를 통해 즉각적으로 힙 자료형으로 변환할 수 있다.
heap = [50 ,10, 20]
heapq.heapify(heap2)
print(heap)
-------
output
[10, 50 ,20 ]
원소 삭제
heappop 함수는 가장 작은 원소(최소힙 기준)를 힙에서 제거함과 동시에 그를 결괏값으로 리턴한다.
result = heapq.heappop(heap)
print(result)
print(heap)
-------
output
10
[20, 50]최대 힙
heapq에서는 최대 힙을 제공하지 않는다. 따라서 다음과 같이 부호를 변경하는 방법을 사용해서 최대 힙을 구현한다. 부호를 바꿔서 최소 힙에 넣어준 뒤에 최솟값부터 pop을 해줄 때 다시 부호를 바꿔주면 최대 힙과 동일하다.
import heapq as hq
a=[]
while True:
n=int(input())
if n==0:
if len(a)==0:
print(-1)
else:
print(-(hq.heappop(a)))
elif n==-1:
break
else:
hq.heappush(a, -n)참고
