[APS] 20. 힙(heap) 에 대해서 복기하기

1. 힙(Heap) 이란?

여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진 트리

짧게 힙(Heap)이라고 줄여서 부르기도 한다. 힙은 항상 완전 이진트리의 형태여야 한다.

출처 : 나무위키

1. 완전 이진트리?

포화 이진트리 ( 모든 잎의 level 이 동일한 이진트리. 잎이 아닌 노드들은 모두 2개의 자식을 갖는 트리 ) 를 오른쪽 leaf 부터 제거해서 얻어진 트리.

2. 시간 복잡도

데이터의 삽입과 삭제에는

$$O(log(N))$$

의 복잡도가 소요된다고 한다.

3. 우선순위 큐와 힙

일반적인 큐(Queue)는 First in-First Out 구조입니다.

즉, 어떤 부가적인 조건 없이 먼저 들어온 데이터가 먼저 나가는 구조였습니다.

하지만 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것 것을 말합니다.

출처 : Chan Blog

최대 힙(Max Heap)은 완전 이진트리이면서, 루트 노드로 올라갈수록 저장된 값이 커지는 구조입니다.

반대로 최소 힙(Min Heap) 은 완전 이진트리이면서, 루트 노드로 올라갈수록 값이 작아지는 구조입니다.

2. Python으로 힙 사용하기

python에서는 내장모듈로 heapq를 제공한다.

from heapq import heappush, heappop

from heapq import heappush, heappop
heap = []

heappush(heap, 4)
heappush(heap, 1)
heappush(heap, 7)
heappush(heap, 3)
print(heap) # [1, 3, 7, 4]

print(heappop(heap)) # 1
print(heap) # [3, 4, 7]

python에서의 heap은 default로 최소힙을 의미한다.

최대힙을 사용하려면 - 를 붙여서 heap push 하는 약간의 트릭이 필요하다.

Uploaded by N2T