[파이썬] 힙 / Heap [Algorithm #5]

Heap(힙)

부모 노드가 자식 노드보다 항상 작거나 큰 값을 가지는 특별한 규칙을 가진 트리를 말한다.

 

부모가 자식보다 작은 값을 가지도록 하는 트리를 최소 힙(Min Heap)이라 하고, 최소 힙의 최상위 노드(Root)는 주어진 값 중 최솟값을 가지게 된다. 반대는 최대 힙(Max Heap)이다.

 

파이썬에서 Heap은 heapq 모듈을 이용하여 구현한다.

• 주어진 리스트를 heapify() 함수를 이용하여 heap으로 만들 수 있다. 기본 상태는 최소 힙이다.
• heap의 첫 번째 값이 root이므로, heap[0]을 통해 값을 읽어올 수 있다.

 

 

 

• heappush(heap, item) 함수로 heap에 원소 item을 넣을 수 있다. heap 상태를 유지함.
• heappop(heap) 함수로 heap의 root를 pop할 수 있다. 

 

 

 

Max Heap 구현하기

heapq 모듈은 최소 힙으로 구현되기 때문에, 원소 그대로의 값과 음수값을 함께 기록하여 정렬한다.

음수를 기준으로 정렬되기 때문에 원소 그대로의 값은 최대 힙으로 정렬된다.

각 원소의 두 번째 원소를 써야 한다는 것에 주의.