Heap

힙이란?
- '최댓값'이나 '최솟값'을 빠르게 찾기 위해 고안된 완전 이진 트리 기반의 자료구조임
- 가장 대표적인 예시는 '토너먼트 대진표'
- 힙의 규칙
  - "부모 노드는 항상 자식 노드보다 강하다(값이 크거나 작다)."
- 토너먼트 대진표
  - "부모 노드(승자)는 항상 자식 노드(패자)보다 강하다."

힙의 종류와 특징

Screenshot 2025-03-05 at 12.14.01 PM.png

최대 힙(Max-Heap)
- 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같은 힙. (부모 노드의 키 $≥$ 자식 노드 키)
- 루트 노드는 최댓값.
- 부모가 자식보다 큰(또는 같은) 구조 유지
- 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
최소 힙(Min-Heap)
- 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같은 힙. (부모 노드의 키 $≤$ 자식 노드 키)
- 루트 노드는 최솟값.
- 부모가 자식보다 작은(또는 같은) 구조 유지
- 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리

핵심 특징

완전 이진 트리
- 힙은 항상 완전 이진 트리의 형태를 유지함
- 이 덕분에 리스트(배열)를 사용해 효율적으로 구현할 수 있다
부모-자식 인덱스 관계 (0-based index)
- 부모 인덱스: (자식 인덱스 - 1) // 2
- 왼쪽 자식 인덱스: (부모 인덱스 * 2) + 1
- 오른쪽 자식 인덱스: (부모 인덱스 * 2) + 2
- 예시 : [1, 3, 2, 4, 5, 8] 리스트를 트리 구조로 읽기
  - 루트 1 (index 0)의 자식:
    - 왼쪽: (0 * 2) + 1 = 1 → heap[1]은 3
    - 오른쪽: (0 * 2) + 2 = 2 → heap[2]은 2
  - 노드 3 (index 1)의 자식:
    - 왼쪽: (1 * 2) + 1 = 3 → heap[3]은 4
    - 오른쪽: (1 * 2) + 2 = 4 → heap[4]은 5
```
      1
     / \\
    3   2
   / \\   /
  4   5 8
```
시간 복잡도
- 최대/최솟값 조회: $O(1)$
- 데이터 삽입/삭제: $O(logN)$ (트리의 높이에 비례)

핵심 연산

⇒ 새로운 데이터가 추가되거나 기존 데이터가 삭제될 때, '힙의 규칙'을 다시 만족시키도록 구조를 재조정하는 것이 중요함

삽입 (push)

→ 일단 맨 끝에 추가하고, 이길 때까지 위로 올라감
1. 새로운 데이터를 완전 이진 트리의 마지막 위치에 추가
2. 새로운 데이터와 부모 노드의 값을 비교
3. 만약 자식의 값이 부모보다 크다면(최대 힙 기준), 둘의 위치를 교환(swap)
4. 새로운 데이터가 제자리를 찾을 때까지(부모보다 작거나, 루트에 도달할 때까지) 이 과정을 반복(이를 sift-up 또는 heapify-up이라고 함)
삭제 (pop)

→ 우승자(루트)를 빼내고, 맨 끝의 후보를 데려와 아래로 내려보냄
1. 루트 노드(최댓값 또는 최솟값)를 제거하고 따로 보관
2. 가장 마지막에 있던 노드를 루트 자리로 이동시킴
3. 새로운 루트가 자식 노드들보다 작다면(최대 힙 기준), 더 큰 자식과 위치를 교환
4. 새로운 루트가 제자리를 찾을 때까지 이 과정을 반복하며 아래로 내려감 (이를 sift-down 또는 heapify-down이라고 합니다.)

힙의 핵심 활용 : 우선순위 큐

힙의 "항상 최댓값/최솟값을 빠르게 찾을 수 있다"는 특징은 우선순위 큐(Priority Queue)를 구현하는 데 적합함
우선순위 큐는 데이터가 들어온 순서가 아니라, 우선순위가 높은 순서대로 처리해야 할 때 사용됨
- 다익스트라 최단 경로 알고리즘
  
  : 다음으로 탐색할 노드 중, 거리가 가장 짧은 노드를 우선적으로 선택할 때
- 운영체제 작업 스케줄링
  
  : 여러 작업 중 우선순위가 가장 높은 작업을 먼저 처리할 때

⇒ 파이썬에서는 heapq 모듈이 최소 힙 기반의 우선순위 큐 기능을 기본으로 제공함

heapq 모듈