[자료구조] 힙(Heap)

1. 힙?

- 힙은 최댓값이나 최솟값을 하기 위해 사용되는 완전 이진트리 형태의 자료구조이다.

- 부모 노드는 항상 자식 노드보다 더 높은 우선순위를 가진다.

- 힙은 완전 이진트리로 정렬된 구조가 아니다.

- 부모 노드가 자식 노드보다 항상 작은 힙을 최소 힙, 부모 노드가 자식 노드보다 큰 힙을 최대 힙이라 한다.

- 형제 노드 간의 대소 관계가 보장되는 이진 탐색 트리와 다르게 힙은 형제 노드 간의 대소 관계는 보장되지 않는다.

- 힙은 부모 노드와 자식 노드 간의 대소 관계만을 보장한다.

- 우선순위 큐와 힙은 다른 개념이다. 우선순위 큐는 각 원소들이 우선순위를 갖는 추상적인 자료형으로 여러 방법으로 구현할 수 있는데 그중에서 힙을 많이 사용하는 것이다.

 

최대힙, 이진 탐색 트리와 다르게 좌우의 상하관계는 보장되지 않는다

 

2. 최소 힙과 최대 힙의 비교

최소힙과 최대힙의 비교

 

파이썬에서는 최소 힙만 구현되어 있고 최대 힙은 별도로 모듈에 구현되어 있지 않다.

heapq 모듈을 사용하면 최소 힙을 사용할 수 있고 간단한 작업을 통해 최대 힙으로 사용할 수도 있다.

 

import heapq

min_heap = []
max_heap = []
nums = [6, 11, 29, 37, 100, 28, 50, 41, 60]
for num in nums:
    heapq.heappush(min_heap, num)
    heapq.heappush(max_heap, -num)
print('최소힙: ', min_heap)
print('최대힙: ', max_heap)​

최대 힙으로 사용하고 싶을 때는 음수로 값을 저장하고 꺼낼 때 다시 음수 처리를 하면 최대 힙처럼 사용할 수 있다