Heap

📗 Heap

• 데이터에서 최대, 최소값을 빠르게 찾고자 고안된 완전 이진 트리

  • 부모 노드 idx = 자식 노드 idx // 2
  • 왼쪽 자식 노드 idx = 부모 노드 idx * 2
  • 오른쪽 자식 노드 idx = 부모 노드 idx * 2 + 1
  • 따라서 배열로 구현 시 idx를 1부터 시작하는 것이 편함

• 우선순위 큐와 같이 최대, 최소를 빠르게 찾아야 하는 알고리즘에 활용됨

• heap은 max heap, min heap으로 나뉨

  • max heap은 자식 노드보다 부모 노드의 값이 큼
  • min heap은 자식 노드보다 부모 노드의 값이 작음
  • 형제 노드 간에는 대소관계가 성립하지 않음

• heap은 중복을 허용하며 노드가 왼쪽부터 채워짐

• min heap은 최소값을 빠르게 찾기 위한 알고리즘이므로, 작은 순서대로 정렬되어 있을거라 생각하지 말아야 함!

• heap 자료구조를 사용하면 효율적인 방식으로 우선순위 큐를 구현할 수 있음

🔔 VS 이진 탐색 트리

• 이진 탐색 트리의 경우 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 순으로 이루어짐
• heap은 어느쪽의 노드 값이 크든 상관이 없음
• heap은 최대 / 최소 검색, 이진 탐색 트리는 탐색을 위한 구조임

🔔 데이터 삽입

• 기본적으로 노드는 왼쪽 최하단부 노드부터 채워짐
• 부모 노드 값보다 큰 경우 부모 노드와 위치를 바꾸며 이를 반복함

🔔 데이터 삭제

• 최대 또는 최소를 알아내는 것이 목표이므로 max heap의 경우 데이터 삭제 시 가장 큰 부모 노드(루트) 값이 삭제됨
• 그 후 가장 최하단부 노드를 루트로 옮김
• 부모 노드보다 큰 자식 노드가 있는지 비교하고 위치를 바꿈(swap)

🔔 heap functions

• heapq 모듈의 경우 list를 min heap처럼 다룰 수 있게 함
• heapq.heappush(heap, item) : item을 heap에 추가함
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop하고 return
• heapq.heapify(x) : list x를 heap으로 변환함
• heap[idx] : 최소값을 삭제하지 않고 단순히 읽음

🔔 heapq를 이용한 max heap 구현

• 각 값에 대한 우선 순위를 구한 후 (우선 순위, 값) 구조의 tuple을 heap에 추가하거나 삭제함
• heap에 원소 추가 시 y = -x 변환을 하면 최솟값 정렬이 최댓값 정렬로 바뀐다는 개념을 활용해 (-item, item)의 tuple 형식으로 넣어줌
• heap에서 값을 읽어올 때는 각 tuple에서 idx 1에 있는 값을 취함

# example
import heapq
numx = [4,1,7,3,8,5]
heap = []
for n in nums:
	heapq.heapppush(heap, (-n, n)) # (우선 순위, 값)
while heap:
	print(heapq.heappop(heap)[1]) # idx 1

8 7 5 4 3 1 # 실행 결과

🔔 heap 직접 구현

• heap 동작 구현

📘 관련 문제

⭐ 더 맵게
⭐ 디스크 컨트롤러
⭐ 이중우선순위큐