[트리] 힙 자료구조 / 파이썬의 heapq 모듈

힙은 특정한 규칙을 가지는 트리이다.

 

규칙에 따라 최대힙, 최소힙으로 나뉘며, 최대 힙은 부모 노드가 자식 노드보다 크고, 최소 힙은 부모 노드가 자식 노드보다 작다.

 

최대 힙의 예제

최대힙이나 최소힙을 구축하기 위해서는 규칙만 다르고 모두 동일하다.

 

무작위 배열에서의 최대 힙은 max.heapify(n) 연산을 통해 생성되는데, 과정은 아래와 같다.

 

1. 현재 노드와 자식 노드의 값을 비교한다.

2. 현재 노드의 값이 가장 크지 않으면 자식 노드 중 가장 큰 값과 현재 노드의 값을 바꾼다.

3. 만약 자식 노드가 없거나 현재 노드의 값이 가장 크면 연산 종료.

4. 맞바꾼 자식 노드의 위치를 현재 노드로 하여 1~3을 반복.

 

계속해서 맞바꿔가면 되기에 이론은 생각보다 쉽다.

참고로 max.heapifiy(n)에서 n은 노드의 번호이다. 번호 아래로 최대 힙으로 정렬하는 것.

 

파이썬의 모듈은 heapq라고 해서, heapq 알고리즘을 제공한다.

여기서는 최소 힙의 형태로 정렬이 된다.

 

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의 함수를 호출할 때마다 리스트를 인자에 넣는다.

 

import heapq

heap = []
heapq.heappush(heap, 30)
heapq.heappush(heap, 70)
heapq.heappush(heap, 10)

print(heap)

>> [10,70,30]

 

만약 리스트가 있다면 바로 힙 자료형으로 만들 수도 있다.

 

li = [70 ,10, 30]
heapq.heapify(li)

print(heap2)

>> [10, 70, 30]

 

원소 삭제

heappop 함수를 사용하면 가장 작은 원소를 힙에서 제거하고 결과값을 반환한다.

result = heapq.heappop(li)

print(result)
print(li)

>> 10
>> [70,30]

 

최대 힙 만들기

최대 힙을 만드려면 간단하다.  heapush를 할 때 -값으로 넣어주면 된다.

그러면 큰 숫자부터 출력이 된다.

import heapq

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

# 아래 for문을 실행시키고 나면 heap은 [-5,-4,-3,-1,-2]가 된다.
for value in values:
	heapq.heappush(heap, -value)

# 아래 for문을 실행시키면 5,4,3,2,1이 출력된다. 즉, 큰 숫자부터 출력이 된다.
for i in range(5):
	print(-heapq.heappop(heap))