힙 이론

1️⃣ 이진 트리(Binary Tree)란?

// 각 노드는 최대 2개의 자식을 가진다 (0개, 1개, 2개)

• 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다.
• 구조적 제약 없이 단순히 자식 수만 제한된 트리입니다.

---

2️⃣ 이진 검색 트리(Binary Search Tree: BST)

// 왼쪽 자식은 작고, 오른쪽 자식은 크다

• BST는 정렬된 형태의 이진 트리입니다.
• 왼쪽 서브트리 < 현재 노드 < 오른쪽 서브트리 관계를 가집니다.
• 하지만 삽입 순서에 따라 한쪽으로 쏠리는 편향 트리가 될 수 있음.

📌 예시 이미지 (BST 최소값/최대값 경로):

---

3️⃣ 힙(Heap) 트리란?

// 부모 노드는 항상 자식 노드보다 크거나 같다 (Max Heap 기준)

✔ 힙 트리 1법칙

• Max Heap: 부모 노드 ≥ 자식 노드
• Min Heap: 부모 노드 ≤ 자식 노드
• 우선순위에 따라 최대값/최소값을 루트로 유지하는 구조

✔ 힙 트리 2법칙

• 완전 이진 트리(Complete Binary Tree) 구조를 가져야 한다.
  • 마지막 레벨을 제외한 모든 레벨이 꽉 차 있어야 한다.
  • 마지막 레벨은 왼쪽부터 순서대로 채워야 한다.

📌 완전 이진 트리 예시:

---

4️⃣ 힙 트리 vs BST 비교

항목	힙 트리 (Heap)	이진 검색 트리 (BST)
정렬 규칙	부모 ≥ 자식 (Max)	왼쪽 < 부모 < 오른쪽
트리 형태	완전 이진 트리	균형 X (편향될 수 있음)
최댓값/최솟값 접근	O(1) (루트)	O(logN) ~ O(N)
삽입/삭제	O(logN)	O(logN) (평균)
구현 난이도	낮음 (배열 사용)	높음 (트리 재조정 필요)

---

5️⃣ 힙 트리 구현 방법

// 배열로 표현
int left = (2 * i) + 1;
int right = (2 * i) + 2;
int parent = (i - 1) / 2;

• 힙은 배열로 쉽게 구현할 수 있는 트리입니다.
• 부모와 자식 노드 간 인덱스 관계를 수식으로 계산할 수 있어 성능과 메모리 효율이 뛰어납니다.

---

6️⃣ 힙에 값 삽입 (Push)

📌 삽입 과정 (도장깨기 ↑)

1. 배열의 마지막 위치에 삽입 (트리 구조 유지)
2. 부모 노드와 비교
3. 부모보다 값이 크면 swap (반복)

void Push(int value) {
    heap.push_back(value);
    int child = heap.size() - 1;

    while (child > 0) {
        int parent = (child - 1) / 2;
        if (heap[parent] >= heap[child])
            break;
        swap(heap[parent], heap[child]);
        child = parent;
    }
}

---

7️⃣ 힙에서 최대값 꺼내기 (Pop)

📌 삭제 과정 (역 도장깨기 ↓)

1. 루트(최대값)를 제거
2. 마지막 노드를 루트로 옮김
3. 자식 노드와 비교하며 내려가기 (Heapify)

void Pop() {
    swap(heap[0], heap.back());
    heap.pop_back();

    int parent = 0;
    while (true) {
        int left = (2 * parent) + 1;
        int right = (2 * parent) + 2;
        int largest = parent;

        if (left < heap.size() && heap[left] > heap[largest])
            largest = left;
        if (right < heap.size() && heap[right] > heap[largest])
            largest = right;

        if (largest == parent)
            break;

        swap(heap[parent], heap[largest]);
        parent = largest;
    }
}

---

8️⃣ 힙의 장점과 응용

• 우선순위 큐 구현에 필수적입니다.
• 다익스트라 알고리즘, A* 알고리즘 등에서 가장 적절한 후보를 빠르게 꺼내야 할 때 매우 유용합니다.
• 기존 자료구조(Vector 등)는 최대값 탐색 시 O(N) 시간이 걸리지만,
  • 힙은 삽입/삭제/탐색 모두 O(logN) 시간 복잡도로 효율적입니다.

---