힙(Heap) = 우선 순위 큐

Heap이란?

• Heap의 영어단어 뜻은 '쌓다', '더미' 라는 뜻
• 데이터에서 최대값과 최소값을 빠르게 찾기 위해 만들어진 완전이진트리
  • 이진트리(binary tree) : 모든 노드들의 자식 노드가 두개 이하인 트리
  • 완전이진트리(complete binary tree) : 부모, 왼쪽자식, 오른쪽자식 순으로 채워지는 트리
• 루트에 최대값이 있는 Max Heap과 루트에 최소값이 있는 Min Heap으로 구분됨
• Max Heap의 경우 Heap의 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 커야함
• Min Heap의 경우 반대로 각 노드의 값은 해당 노드들의 자식 노드가 가진 값보다 작아야함
• Heap은 좌측부터 채워나가지만 형제 노드들간에는 좌/우 불문하고 크기를 구분하지 않음

Heap과 Binary Search Tree의 차이

• 둘다 이진트리이다.
• Binary Search Tree는 왼쪽 자식노드 < 부모노드 < 오른쪽 자식노드의 순으로 크기가 큼
• Heap은 크기 순서가 없음 => 루트값만 고정 => 최소힙이면 루트값이 최소값, 최대힙이면 루트값이 최대값
• 따라서, Binary Search Tree는 탐색용 자료구조에 사용. Heap은 최대, 최소 검색을 위한 자료구조로 사용

Heapfify란?

• heapify는 일반 배열을 heap 자료구조로 만드는 과정

Min Heap 예시

• [2, 6, 9, 4, 7, 1] 순으로 데이터가 추가될때 Min Heap 구조로는 다음과 같이 처리된다 => [1, 4, 2, 6, 7, 9]
  

Python Heap 사용

• heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공
• 자바에 익숙하신 분이라면 PriorityQueue 클래스를 생각하시면 이해가 쉬우실 것 같습니다.
• min heap에서 가장 작은값은 언제나 인덱스 0, 즉, 이진 트리의 루트에 위치

사용

• heap은 list만들때와 같음 => heap = [] => 이상태에서 heapq 모듈의 메소드를 사용하면 heap구조를 사용하는것
• 최소힙에선 idx 0 => 최소값 / 최대힙에선 idx 0 => 최대값
  • (주의사항) 최소힙에서 인덱스 0에 가장 작은 원소가 있다고 해서, 인덱스 1에 두번째 작은 원소, 인덱스 2에 세번째 작은 원소가 있다는 보장은 없다는 것입니다.
• 시간복잡도
  • 내부적으로 이진 트리에 원소를 추가하는 heappush() 함수는 O($\log_2N$

# 모듈 임포트
import heapq

# heap은 list만들때와 같음 => 메소드사용이 다르다고 생각하자
heap = []

# heap에 원소추가
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap)
#[1, 3, 7, 4]

# 힙에서 원소 삭제
print(heapq.heappop(heap))
#1
print(heap)
#[3, 4, 7]

# 아래 코드를 통해서 가장 작았던 1이 삭제되어 리턴되었고, 그 다음으로 작었던 3이 인덱스 0으로 올라온 것을 확인 가능
print(heapq.heappop(heap))
#3
print(heap)
#[4,7]

# 최소값 선택하는 방법(pop처럼 삭제하는게 아니라 그냥 조회만 한다 or 그냥가져온다)
print(heap[0])
#4

# 기존 시르스틀 힙으로 변환해주기(heapify)
heap = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap)
print(heap)
#[1, 3, 5, 4, 8, 7]

(참고) 최대힙은 어떻게 사용?

• 최대 힙을 만들려면 각 값에 대한 우선 순위를 담는 튜플을 만들어서 힙에다 담아주면된다.
• 이때 튜플은 (우선 순위, 값) 형태인데 (-값, 값) 으로 넣어주면 값이 클수록 우선수위 -값은 작아져서 우선순위가 높아져서 => 최대힙 구조를 얻을 수 있음
• 그리고 이 힙에는 튜플들이 담겨있기때문에 값(value)를 가져오고 싶을땐 for문/while문으로 element를 하나씩 가져와서 값(value)이 있는 idx 1을 선택하면 됨

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

References

• https://redcrow.tistory.com/487
• python-heap 활용