우선순위 큐(Priority Queue)

• 우선순위 큐는 값을 넣을 때마다 자동으로 우선순위에 따라 정렬되는 큐
• 꺼낼 때 가장 우선순위가 높은 값을 먼저 꺼냄
  
  
• 최대 힙 (Max-Heap): 가장 큰 값이 우선순위 1위
• 최소 힙 (Min-Heap): 가장 작은 값이 우선순위 1위

힙(Heap)

• 힙(Heap)은 우선순위 큐를 구현하기 위한 자료 구조
• 힙은 이진트리 형태로 구성되며, 다음과 같은 규칙을 따름:
  • 규칙 1: 노드를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워나간다. (레벨 순서로 노드를 삽입한다.)
    • 위 그림은 모두 이진트리인데, (a)는 힙이지만 (b)는 힙이 아니다.
    • (b)는 왼쪽부터 채워야 한다는 규칙을 벗어났다.
  • 규칙 2: 최소 힙은 부모 노드가 자식 노드의 값보다 작거나 같아야 한다. 파이썬의 heapq 모듈은 최소 힙(min heap)이다. (최대 힙은 부모 노드가 자식 노드의 값보다 크거나 같다.)
• 루트 노드에 항상 우선순위가 가장 높은 값이 위치
• 정렬 개념은 없고, 단지 부모 > 자식 조건만 지키면 됨

  이유	설명
  완전 이진 트리	위→아래, 왼→오 순서로 꽉 채워야 함
  부모 > 자식 조건만 존재	10이 루트라면 3, 5, 1은 어디 있든 상관 없음 (단, 부모보다 작기만 하면 됨)
  정렬 X	정렬은 목표가 아님. 가장 큰 값을 빠르게 꺼내기 위한 구조가 목적

  삽입: 5 → 3 → 10 → 1
  
          10
         /  \
        3    5
       /
      1

파이썬에서 힙(Heap) 구현하기

• 파이썬에서는 heapq 모듈은 배열(리스트)을 이용하여 완전 이진트리를 구현 heappush(heap, data): 힙에 새로운 데이터를 삽입
  heappop(heap): 힙에서 루트 노드(최소값)를 꺼낸 후 삭제
  heapify(x): 주어진 배열을 힙 구조로 변환
  

• 시간 복잡도는 O(log n)