---

📍 힙

영단어 힙(heap)은 '무엇인가를 차곡차곡 쌓아올린 더미'라는 뜻
힙이란 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조

참고) 완전이진트리: 트리의 위부터 아래, 왼쪽부터 오른쪽의 순서로 빠짐없이 가득 차있는 이진 트리
(마지막 레벨은 제외)

A가 B의 부모노드(parent node)이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다는 속성 만족함
참고) 형제 사이에는 대소관계가 정해지지 않음

두가지 종류의 힙
1. 최대 힙: 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙
2. 최소 힙: 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙

힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징
=> 우선순위 큐와 같은 추상적 자료형을 구현할 수 있음

🔹 파이썬에서의 힙

파이썬 heapq 모듈은 heapq(priority queue) 알고리즘을 제공함
이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공

import heapq # 모듈 임포트
# 파이썬의 보통 리스트를 마치 최소 힙처럼 다룰 수 있도록 도와줌

heap = [] 
heapq.heappush(heap, 1) # 노드 추가: heappush 메소드 이용
heapq.heappush(heap, 7)

return heapq.heappop(heap) # 노드 삭제: heappop 메소드 이용 (가장 작은 원소를 꺼내어 리턴, 자동적으로 그 다음으로 작은 원소가 루트노트가 됨)
print(heap[0]) # 최소값을 꺼내지 않고 리턴만 하려면 인덱스로 접근하기

tmp = [7, 5, 8, 3]
heapq.heapify(tmp) # 기존에 사용한 리스트를 힙으로 변환: heapify 메소드 이용, 시간 복잡도는 O(N)

🔹 응용

최대 힙

# 힙에 튜플(tuple)을 원소로 추가하거나 삭제하면, 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리를 이용

# 각 값에 대한 우선 순위를 구한 후,
# (우선 순위, 값) 구조의 튜플(tuple)을 힙에 추가하거나 삭제하면 됨
# 그리고 힙에서 값을 읽어올 때는 각 튜플에서 인덱스 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

# 결과
# 8
# 7
# 5
# 4
# 3
# 1    

K번째 최소값/최대값

# 주어진 배열로 힙을 만든 후, heappop() 함수를 K번 호출
import heapq

def kth_smallest(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)

    kth_min = None
    for _ in range(k):
        kth_min = heapq.heappop(heap)
    return kth_min

print(kth_smallest([4, 1, 7, 3, 8, 5], 3))

# 결과
# 4

힙 정렬

import heapq

def heap_sort(nums):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)

    sorted_nums = []
    while heap:
        sorted_nums.append(heapq.heappop(heap))
    return sorted_nums

print(heap_sort([4, 1, 7, 3, 8, 5]))

# 결과
# [1, 3, 4, 5, 7, 8]

---

📍 우선순위 큐

우선순위 큐는 평범한 큐나 스택과 비슷한 축약 자료형, 그러나 각 원소들은 우선순위를 갖고 있음!
높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리됨
(두 원소의 우선순위가 같다면 queue의 순서에 따라 처리됨)

참고) 큐: 원소들은 선입 선출 순으로 처리됨

참고) 우선순위 큐가 힙이다? (X)
우선순위 큐는 "리스트"나 "맵"과 같이 추상적인 개념임
마치 리스트는 연결 리스트나 배열로 구현될 수 있는 것과 같이, 우선순위 큐는 힙이나 다양한 다른 방법을 이용해 구현될 수 있음

🔹 구현 방식: 배열, 연결 리스트, 힙

구현 방법	enqueue()	dequeue()
배열	O(1)	O(N)
연결 리스트	O(1)	O(N)
정렬된 배열	O(N)	O(1)
정렬된 연결 리스트	O(N)	O(1)
힙	O(logN)	O(logN)

힙 방식은 최악의 경우라도 O(logN)을 보장하기 때문에 일반적으로 힙을 가지고 구현함

---