[자료구조] 힙(heap), 우선순위큐, 파이썬 최대힙, 최소힙

힙이란?

---

• 완전 이진트리의 일종으로 우선순위큐(PriorityQueue)를 위하여 만들어진 자료구조
• 큐에 우선순위가 적용되어 있으므로 최대값이나 최소값을 빠르게 찾아내기 위한 자료구조
  (큐는 가장 먼저 들어온 데이터가 먼저 나가지만 우선순위큐는 해당 우선순위 데이터가 가장 먼저 나간다)
• 단 모든 값들이 정렬되어 있지 않은 일종의 반정렬(느슨한 정렬) 상태이며 최소값 혹은 최대값 만을 보장
  (최소 최대가 모두 필요할 때는 이중 힙 구조를 써야함)
• 삽입 및 삭제가 BST보다 빠르며 모든 삭제나 삽입이 배열의 가장 끝에서 발생

힙의 추가

• 추가되는 숫자는 가장 마지막 레벨 빈 자리(왼쪽부터 채워짐)로 저장 됨
• 부모의 숫자가 클 때는 조건을 만족하지 않으므로 부모와 자식을 교환
• 교환이 발생하지 않을 때까지 반복하여 처리

힙의 삭제

• 힙에서 숫자를 꺼낼 때에는 가장 위에 있는 숫자를 선택
• 가장 마지막 레벨 오른쪽에 있는 숫자를 가장 위로 보냄
• 부모늬 숫자가 자식 숫자보다 작은 경우 자식의 좌우 중 작은쪽과 교환함
• 교환이 발생하지 않을 때까지 반복하여 처리

---

최대 힙

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리최소 힙
• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
• 파이썬 pop 메서드는 가장 작은 항목을 반환함

언제 힙, 우선순위큐를 사용하는가?

---

• 삽입작업과 최대/최소값을 pop() 작업이, 각각 O(logN), O(1) 밖에 걸리지 않는다.
• 힙에 값을 삽입을 한 번에 하는 것이 아니라 여러 번에 걸쳐서 한다.
• 여러 시점에 해당 시점의 최소 혹은 최대값을 요구한다.
• 위와 같은 삽입, 최대/최소값 확인이 여러차례 필요하다.

파이썬에서 힙, 우선순위큐의 활용

---

파이썬 설명서를 참고하세염

heapq.heappush(heap, item)

• 힙 불변성을 유지하면서, item 값을 heap으로 푸시heapq.heappop(heap)
• 힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환
• 힙이 비어 있으면, IndexError가 발생(팝 하지 않고 가장 작은 항목에 액세스하려면, heap[0] 사용)

파이썬에서 최대힙의 활용

---

• heapq 모듈은 최소 힙(min heap)을 기능만을 동작
• 따라서 힙에 (우선 순위, 값) 구조의 튜플(tuple)을 원소로 추가하거나 삭제하면, 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리를 이용할 수 있다.
• 힙에서 값을 읽어올 때는 각 튜플의 인덱스 1값을 취하면 되고 예제로 확인 가능하다.

import heapq as hq

nums = [10, 15, 1, 4, 6]
heap = []

for num in nums:
  hq.heappush(heap, (-num, num))

priority, num = hq.heappop(heap)
print(num

---

예제 문제

• 프로그래머스 더 맵게
• ㅍ로그래머스 섬 연결하기

단어 정리

• 완전 이진 트리 : 마지막 레벨을 제외한 모든 레벨의 노드가 완전히 채워져 있는 구조
• 우선순위큐 : 큐 자료구조에 우선순위가 있는 구조