6. Heap - 파이썬 힙 공부하기

힙

특정한 규칙을 가지는 트리로, 최댓값과 최솟값 추출 연산을 효율적으로 하기 위해 고안된 완전이진트리 구조

최소힙	부모 노드 키값이 자식 노드의 키값보다 항상 작은 힙
최대힙	부모 노드 키값이 자식 노드의 키값보다 항상 큰 힙

최대힙의 예시(출처 : 힙 (자료 구조) - 위키백과, 우리 모두의 백과사전 (wikipedia.org))

# 위 그림의 list표현에서 2k+1과 2k+2는 k번째 노드의 자식 노드들이 된다.

# 위 그림의 list표현에서 k번째 노드의 부모 노드는 (k-1)//2가 된다.

 

주의할 점

힙은 정렬된 구조가 아니다. 상/하 관계는 있으나, 좌/우 관계는 없다.

추출 메서드 자체는 O(1)이지만, 재정렬 과정이 필요하기 때문에 O(logn)이 된다.

→ 삽입, 추출 모두 O(logn) 

 

파이썬에서 힙 사용법

파이썬은 heapq 모듈을 제공한다. 내부적으로는 리스트를 활용한 최소 힙의 형태이다.

삽입	heapq.heappush(heap, item)	item을 heap에 추가
추출	heapq.heappop(heap)	heap에서 가장 작은 원소를 pop 비어 있는 경우 IndexError가 호출됨.
힙변환	heapq.heapify(x)	리스트 x를 즉각적으로 heap으로 변환함 O(n)