힙 자료구조
- 모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리(binary tree) 구조.
파이썬에서는 인덱스 0에서 시작해 k번째 원소가 항상 자식 원소들(2k+1, 2k+2) 보다 작거나 같은 최소 힙 형태로 정렬 - 여러개의 값들 중 최댓값 또는 최솟값을 빠르게 찾아내기 위하여 고안된 자료구조
- 힙은 중복된 값을 허용한다. (이진 트리는 중복 값을 허용하지 않는다.)
- 파이썬 내의 내장 모듈. 별도의 설치 작업 없이 바로 사용 (import heapq 만 하면 됨.)
힙 함수
-
heapq.heappush(heap, item) : item을 heap에 추가
-
heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨.
-
min heap에서 가장 작은 값은 언제나 인덱스 0, 이진트리의 루트에 위치함.
(ex) heap=[10,50,20] 일때, result = heapq.heappop(heap) 값은 10
- heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환 (in linear time, O(N) )
heap2 = [50 ,10, 20]
heapq.heapify(heap2) # [10,50,20]
print(heap2) 파이썬에서 최대 힙 만들기
- 파이썬의 heapq 모듈은 최소 힙으로 구현되어 있기 때문에 최대 힙 구현을 위해서는 별도의 작업이 필요함.
- 힙에 원소를 추가할 때 (-item, item)의 튜플 형태로 넣어주면 튜플의 첫 번째 원소를 우선순위로 힙을 구성. (문제에도 많이 활용됨 (ex) 무지 먹방)
heap_items = [1,3,5,7,9]
max_heap = []
for item in heap_items:
heapq.heappush(max_heap, (-item, item))
print(max_heap)- heappop을 사용하게 되면 힙에 있는 최댓값이 반환
- 실제 원소 값은 튜풀의 두번째 자리에 있으므로 [1] 인덱싱을 통해 접근한다.
max_item = heapq.heappop(max_heap)[1]
print(max_item) # 9시간 복잡도
heappush() - O(logN)
heapop() - O(logN)
heapify() - O(N)
공부방