맥스 힙

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

1 개념

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

2 특징

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

3 배열에서의 인덱스 관계

• 부모 인덱스 i에 대해:
  • 왼쪽 자식: 2i + 1
  • 오른쪽 자식: 2i + 2
• 자식 인덱스 j에 대해:
  • 부모: (j - 1) // 2

4 연산

4.1 1. 삽입 (Insert)

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

4.2 2. 삭제 (Extract Max)

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

4.3 3. 최대값 확인 (Peek Max)

• 루트 노드를 그대로 반환 (삭제 없음)

5 파이썬 예시

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

6 시각적 예시

초기 배열: [20, 15, 18, 8, 10, 5] 트리 형태:

         20  
       /    \  
     15      18  
    /  \     /  
   8   10   5

7 활용

• 힙 정렬
• 우선순위 큐
• 스케줄링 알고리즘
• 최대값 유지 알고리즘

8 비교

• 맥스 힙: 최댓값이 루트
• 민 힙: 최솟값이 루트

9 같이 보기

• 힙 정렬
• 우선순위 큐
• 민 힙
• 완전 이진 트리
• 이진 탐색 트리

10 참고 문헌

• Cormen et al. (2009). Introduction to Algorithms. MIT Press
• Sedgewick, R. (2011). Algorithms
• Python heapq 공식 문서