[자료구조] 힙(Heap)

힙(Heap)

최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조 (완전 이진트리를 기본으로 함)
힙 property : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립한다.

• 최소 힙 (Min Heap) : 각 노드의 키 값이 그 자식 노드의 키 값보다 크지 않은 힙
• 최대 힙 (Max Heap) : 각 노드의 키 값이 그 자식노드의 키 값보다 작지 않은 힙
• 시간복잡도 : O(log n)
  
  
  

파이썬의 heapq 모듈은 heap 자료구조를 제공한다.

모든 부모 모드는 그의 자식 노드보다 값이 작거나 큰 이진트리구조이다.

• 인덱스 : k번째 원소가 항상 자식 원소(2k+1, 2k+2) 보다 작거나 같은 최소 힙 형태로 정렬됨
  
  

heapq모듈의 함수들

• heapq.heappush(heap, item) : heap에 item 추가
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & return. 비어 있을 경우 IndexError
• heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환 O(N)
  
  

최대 힙

파이썬에서 제공하는 heapq는 최소 힙을 지원한다. 그렇다면 최대 힙은 어떻게 만들 수 있을까?

heapq.heappush(max_heap, (-item, item))

(-item, item)의 튜플 형태로 넣어 정렬한 뒤 heapq.heappop(max_heap)[1]로 접근할 수 있다.

---

Reference

• [Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기 - LittleFox