[Python] 힙 (Heap)

힙(Heap)의 특징

• 힙은 완전 이진 트리 자료구조의 일종
• 힙에서는 항상 루트 노드(root node)를 제거
• 최소 힙(min heap)
  • 루트 노드가 가장 작은 값을 가짐
  • 따라서 값이 작은 데이터가 우선적으로 제거 됨
• 최대 힙(max heap)
  • 루트 노드가 가장 큰 값을 가짐
  • 따라서 값이 큰 데이터가 우선적으로 제거 됨

완전 이진 트리 (Complete Binary Tree)

• 루트(root) 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리(tree)를 의미
  

최소 힙 구성 함수: Min-Heapify()

• (상향식) 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체한다
  

힙에 새로운 원소가 삽입될 때

• 새로운 원소가 삽입되었을 때 O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다

1. 삽입하고자 하는 값을 트리의 가장 마지막 원소에 추가
2. 부모노드와의 대소관계를 비교하면서 만족할 때까지 자리 교환을 반복
   

힙에서 원소가 제거될 때

• 원소가 제거되었을 때 O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다
  - 원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 한다
  
  - 이후에 루트 노드에서부터 하향식으로 (더 작은 자식 노드로) Heapify()를 진행한다
  

1. 힙에서는 루트 노드만 삭제가 가능하므로 루트 노드를 제거한다
2. 가장 마지막 노드를 루트로 이동시킨다
3. 자식노드와 비교하여 조건이 만족할 때까지 이동시킨다

힙큐 모듈 (heapq module)

• 파이썬에서 제공하는 힙큐 모듈
• 일반적인 리스트를 min heap 처럼 다룰 수 있게 해준다

모듈 임포트

import heapq

노드 추가

• heappush 메소드 이용

heap = []
heapq.heappush(heap, 1)

노드 삭제

• heappop 메소드 이용
• 가장 작은 원소를 꺼내어 리턴, 자동적으로 그 다음으로 작은 원소가 루트노드가 됨

return heapq.heappop(heap)

# 최소값을 꺼내지 않고 리턴만 하려면 인덱스로 접근하기
print(heap[0])

주의할 점: 인덱스 1이 2번째로 작다는 보장은 없으므로 n번째로 작은 원소를 얻고 싶다면 n-1개의 원소를 빼내야 한다

기존에 사용한 리스트를 힙으로 변환하기

• heapify 메소드 이용
• 시간복잡도는 O(n)

tmp = [7, 5, 8, 3]
heapq.heapify(tmp)

최대 힙 만들기

• 우선순위가 포함된 튜플 이용하기

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums :
	heapq.heappush(heap, (-num, num)) # 우선 순위, 값

while heap :
	print(heapq.heappop(heap)[1]) # index 1

---

https://www.youtube.com/watch?v=AjFlp951nz0&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=11
https://www.daleseo.com/python-heapq/