Python_#9

🧱 2. 힙(Heap)

힙은 이진 트리의 한 종류.
특히, “부모 노드가 자식보다 항상 크거나 작다”는 우선순위 구조를 가지고 있다.
힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

💎 힙의 종류

1. 최대 힙 (Max Heap)
   → 부모가 자식보다 항상 크다!

        100
       /   \
      50    70
     /  \
    30   20

→ 제일 큰 값이 항상 루트(맨 위)에 있음.

2. 최소 힙 (Min Heap)
   → 부모가 자식보다 항상 작다!

        10
       /  \
      20   30
     /  \
    40   50

⚙️ 힙의 주요 기능

기능	설명
삽입(insert)	새 원소를 힙에 추가하고, 규칙에 맞게 재정렬
삭제(delete)	루트(최대/최소 값)를 꺼내고, 나머지를 재정렬
정렬(heap sort)	힙을 이용하면 정렬도 가능 (Heap Sort 알고리즘)

💡 힙이 쓰이는 곳

우선순위 큐 (Priority Queue)
→ 예: “가장 긴급한 일 먼저 처리하기”

스케줄러, 경로 탐색 알고리즘 (예: 다익스트라)
→ 빠르게 최소값/최대값 찾기 유용함!

⁉️ 정렬이랑 뭐가 다른가요?

정렬은 항상 O(NlogN) 만큼의 시간 복잡도가 매번 걸리는 연산.
힙이라는 자료구조는, 데이터를 가져오고 빼는 데 O(log(N)) 만큼의 시간 복잡도가 걸리는 대신 매번 정렬을 해주지 않아도 정렬된 상태를 유지할 수 있다!

그래서 정렬이 된 데이터 삽입 삭제가 잦은 상황에서는 힙을 쓰는 것이 더 효율적임.

⁉️ 힙을 구현하려면 어떻게 해야할까요?

힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조.
다시 말하면 부모 노드의 값이 자식 노드의 값보다 항상 커야 함.
그러면 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 감!
따라서 최대의 값들을 빠르게 구할 수 있게 되는 것.

      8      Level 0
    6   3    Level 1
     2 1     Level 2  # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다!

      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
   4 2 1     Level 2  # 자식 노드보다 크니까 힙이 맞습니다!


      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
   4 2 5     Level 2  # 자식 노드보다 크지 않아서 힙이 아닙니다..!
											
- 힙은 다음과 같이 최대값을 맨 위로 올릴수도 있고,
최솟값을 맨 위로 올릴 수도 있습니다!

최댓값이 맨 위인 힙을 Max 힙,
최솟값이 맨 위인 힙을 Min 힙이라고 합니다!

🧠 트리 vs 힙 비교 정리

구분	트리(Tree)	힙(Heap)
구조	계층 구조	완전 이진 트리 형태
정렬 규칙	없음 (자유롭게 배치 가능)	부모 ≥/≤ 자식 (우선순위 있음)
목적	관계 표현, 탐색	우선순위 처리, 정렬
예시	폴더 구조, 조직도	우선순위 큐, 힙 정렬

⚠️ 주의 포인트

• 트리는 “관계 구조”, 힙은 “우선순위 구조”
• 힙은 항상 완전 이진 트리 → 한 층씩 꽉 채워야 함
• 이진 탐색 트리와 헷갈리지 않기!
• BST는 “왼쪽 < 부모 < 오른쪽”
• 힙은 “부모 ≥/≤ 자식”