맥스 힙 편집하기

맥스 힙(Max Heap)은 완전 이진 트리(Complete Binary Tree)의 한 형태로, 모든 부모 노드의 값이 그 자식 노드들의 값보다 '''크거나 같은''' 구조를 갖는 힙 자료구조이다. 우선순위 큐(priority queue) 구현이나 정렬 알고리즘([[힙 정렬]]) 등에 사용된다.

== 개념 ==
* 완전 이진 트리 형태 유지
* 각 노드의 값 ≥ 자식 노드의 값
* '''루트 노드에는 항상 최댓값이 위치'''

== 특징 ==
* 루트 노드에서 최댓값을 O(1)에 가져올 수 있음
* 삽입, 삭제(최댓값 제거) 모두 O(log n)
* 배열로 구현하면 자식과 부모의 인덱스를 수학적으로 계산 가능

== 배열에서의 인덱스 관계 ==
* 부모 인덱스 i에 대해:
** 왼쪽 자식: 2i + 1  
** 오른쪽 자식: 2i + 2  
* 자식 인덱스 j에 대해:
** 부모: (j - 1) // 2

== 연산 ==
=== 1. 삽입 (Insert) ===
# 마지막 위치에 삽입
# 부모와 비교하며 위로 올림 (Heapify-up or Bubble-up)

=== 2. 삭제 (Extract Max) ===
# 루트 노드(최댓값)를 제거
# 마지막 원소를 루트에 올리고, 아래로 내리며 정렬 (Heapify-down or Bubble-down)

=== 3. 최대값 확인 (Peek Max) ===
* 루트 노드를 그대로 반환 (삭제 없음)

== 파이썬 예시 ==
<pre>
import heapq

# 기본 heapq는 Min Heap → 최대 힙은 부호를 반대로
h = []
heapq.heappush(h, -10)
heapq.heappush(h, -5)
heapq.heappush(h, -20)

max_val = -heapq.heappop(h)  # 최대값 추출
print(max_val)  # 20
</pre>

== 시각적 예시 ==
초기 배열: [20, 15, 18, 8, 10, 5]  
트리 형태:  
          20  
        /    \  
      15      18  
     /  \     /  
    8   10   5

== 활용 ==
* [[힙 정렬]]
* [[우선순위 큐]]
* [[스케줄링 알고리즘]]
* [[최대값 유지 알고리즘]]

== 비교 ==
* [[맥스 힙]]: 최댓값이 루트  
* [[민 힙]]: 최솟값이 루트

== 같이 보기 ==
* [[힙 정렬]]
* [[우선순위 큐]]
* [[민 힙]]
* [[완전 이진 트리]]
* [[이진 탐색 트리]]

== 참고 문헌 ==
* Cormen et al. (2009). Introduction to Algorithms. MIT Press
* Sedgewick, R. (2011). Algorithms
* Python heapq 공식 문서
[[분류:자료 구조]]
[[분류:트리]]