[JAVA] ⚙️ 자료구조 : Heap | 간단 정리 및 삽입•삭제 과정 💬

Heap ⚙️

최대 힙 / 최소 힙

---

📌 Heap (힙)

• 완전 이진 트리(Complete Binary Tree) 기반의 자료구조
• 부모 노드와 자식 노드 간의 우선순위 관계를 만족
• 두 가지 종류가 있음:
  • 최대 힙(Max Heap): 부모 ≥ 자식 (부모가 항상 가장 큼)
  • 최소 힙(Min Heap): 부모 ≤ 자식 (부모가 항상 가장 작음)

---

📌 예시

1️⃣ 최대 힙 (Max Heap)

         50
       /    \
     30      20
    /  \    /  \
   15  10  8    16

• 부모 ≥ 자식 규칙 만족 → 루트(50)가 최댓값

 

2️⃣ 최소 힙 (Min Heap)

         5
       /   \
     10     15
    / \    /  \
   20 30  25  40

• 부모 ≤ 자식 규칙 만족 → 루트(5)가 최솟값

---

📌 특징

특징	설명
구조	완전 이진 트리 → 배열로 효율적으로 표현 가능
루트	Max Heap → 최대값 / Min Heap → 최소값
삽입	새로운 원소는 마지막 레벨에 추가 후 위로 Heapify Up (Bubble Up)
삭제	루트 제거 후 마지막 원소를 루트로 올리고 Heapify Down (Bubble Down)

---

🔗 삽입 과정 (예: Max Heap)

초기 상태:

       50
      /
    30

 

40 삽입:

       50
      /  \
    30   40

✅ (40 ≤ 50 → 규칙 유지)

 

60 삽입:

       50
      /  \
    30   40
   /
  60

✅ Heapify Up (Bubble Up): 60 > 30 → 교환

 

       50
      /  \
    60   40
   /
  30

✅ 60 > 50 → 교환

 

최종

       60
      /  \
    50   40
   /
  30

 

---

🔗 삭제 과정 (예: Max Heap)

삭제는 항상 루트(최댓값) 부터

 

초기 상태:

       60
      /  \
    50   40
   /
  30

 

루트(60) 삭제 후 마지막 원소(30)를 루트로 이동:

       30
      /  \
    50   40

✅ Heapify Down: 30 < 50 → 교환

 

최종

       50
      /  \
    30   40

30과 자식 비교 → 규칙 만족 (종료)

---

📌 시간 복잡도

• 삽입 (Insert): O(log n) → 마지막에 넣고 Heapify Up
• 삭제 (Extract Max/Min): O(log n) → 루트 제거 후 Heapify Down
• 최대/최소값 접근: O(1) → 루트 확인

---

📁 활용

• 우선순위 큐 (Priority Queue)
• 힙 정렬 (Heap Sort)
• 다익스트라 알고리즘 (최단 경로 탐색)
• 허프만 코딩 (데이터 압축)

---

✅ 정리

• Heap은 완전 이진 트리 기반의 자료구조
• Max Heap: 부모 ≥ 자식 (루트 = 최대값)
• Min Heap: 부모 ≤ 자식 (루트 = 최소값)
• 삽입 → 아래에 넣고 위로 올림, 삭제 → 루트 빼고 아래로 내림