자료구조 정리 - 힙(Heap)

힙 (Heap)이란?

핵심: 완전 이진 트리 + 부모가 자식보다 크거나 작음

 

힙의 종류

1. 최대 힙 (Max Heap)

• 부모 ≥ 자식
• 루트가 최대값

 

 

      100
     /   \
   80    60
  / \    /
 50  40 30

 

2. 최소 힙 (Min Heap)

• 부모 ≤ 자식
• 루트가 최소값

 

 

       10
     /    \
   20     30
  / \     /
 40  50  60

 

BST vs 힙

BST:

 

 

      50
     /  \
   30    70
  / \    / \
 20 40  60 80

왼쪽 < 부모 < 오른쪽
중위 순회 → 정렬됨

최대 힙:

 

 

      80
     /  \
   70    60
  / \    /
 50 40  30

부모 > 자식 (좌우 상관없음!)
좌우 순서 없음

차이:

• BST: 왼쪽/오른쪽 구분 있음
• 힙: 좌우 구분 없음, 부모-자식 관계만 중요

 

힙의 특징

1. 완전 이진 트리

 

 

올바른 힙:
      10
     /  \
   20    30
  / \   /
 40 50 60

왼쪽부터 차례로 채워짐!

 

 

잘못된 예:
      10
     /  \
   20    30
  /       \
 40       50

중간이 비어있음 X

 

2. 배열로 구현!

이게 힙의 핵심!

 

 

      10
     /  \
   20    30
  / \   /
 40 50 60

배열로:
[10, 20, 30, 40, 50, 60]
 0   1   2   3   4   5

 

배열 인덱스 규칙

인덱스 i 노드:

• 왼쪽 자식: 2i + 1
• 오른쪽 자식: 2i + 2
• 부모: (i - 1) / 2

 

 

[10, 20, 30, 40, 50, 60]
 0   1   2   3   4   5

인덱스 1 (값 20):
- 왼쪽 자식: 2×1+1 = 3 (값 40)
- 오른쪽 자식: 2×1+2 = 4 (값 50)
- 부모: (1-1)/2 = 0 (값 10)

완전 이진 트리라서 배열에 빈 공간 없음!

 

힙 연산

1. 삽입 (Insert)

과정:

1. 배열 맨 끝에 추가
2. 부모와 비교하며 올라감 (Bubble Up)

예시 - 최소 힙에 5 삽입:

 

 

Before:
       10
     /    \
   20     30
  / \
 40  50

배열: [10, 20, 30, 40, 50]

1. 맨 끝에 5 추가
배열: [10, 20, 30, 40, 50, 5]
       10
     /    \
   20     30
  / \     /
 40  50  5

2. 부모(30)와 비교: 5 < 30 → 교환
배열: [10, 20, 5, 40, 50, 30]
       10
     /    \
   20     5
  / \     /
 40  50  30

3. 부모(10)와 비교: 5 < 10 → 교환
배열: [5, 20, 10, 40, 50, 30]
       5
     /   \
   20    10
  / \    /
 40  50 30

끝! (부모보다 작지 않으니 멈춤)

시간복잡도: O(log n) (최대 높이만큼 올라감)

 

2. 삭제 (Delete) - 루트만 삭제

과정:

1. 루트 제거
2. 맨 끝 노드를 루트로
3. 자식과 비교하며 내려감 (Bubble Down)

예시 - 최소 힙에서 루트 삭제:

 

 

Before:
       5
     /   \
   20    10
  / \    /
 40  50 30

배열: [5, 20, 10, 40, 50, 30]

1. 루트(5) 제거, 맨 끝(30)을 루트로
배열: [30, 20, 10, 40, 50]
       30
     /    \
   20     10
  / \
 40  50

2. 자식(20, 10) 중 작은 것(10)과 비교: 30 > 10 → 교환
배열: [10, 20, 30, 40, 50]
       10
     /    \
   20     30
  / \
 40  50

3. 자식 없음 → 끝!

시간복잡도: O(log n)

 

힙의 용도

1. 우선순위 큐 (Priority Queue)

일반 큐:

• 먼저 들어간 게 먼저 나옴 (FIFO)

우선순위 큐:

• 우선순위 높은 게 먼저 나옴

 

 

최소 힙으로 구현:
삽입: [30, 10, 50, 20]

힙:
       10
     /    \
   20     50
  /
 30

꺼내기:
1번째: 10 (가장 작은 것)
2번째: 20
3번째: 30
4번째: 50

 

2. 힙 정렬 (Heap Sort)

과정:

1. 배열을 힙으로 만듦
2. 루트를 하나씩 꺼냄 → 정렬됨

시간복잡도: O(n log n)

 

3. Top K 문제

 

 

문제: 배열에서 가장 큰 K개 찾기

[3, 1, 4, 1, 5, 9, 2], K=3

방법: 크기 3인 최소 힙 사용
1. 처음 3개 넣음: [3, 1, 4]
2. 다음 원소(1): 1 < 3 (최소) → 무시
3. 다음 원소(5): 5 > 1 (최소) → 1 제거, 5 삽입
4. 계속...

결과: [4, 5, 9]

 

힙 vs BST

 

특징	힙	BST
구조	완전 이진 트리	이진 트리
규칙	부모 > 자식	왼쪽 < 부모 < 오른쪽
좌우 순서	없음	있음
구현	배열	포인터
최대/최소	O(1)	O(log n)
탐색	O(n)	O(log n)
용도	우선순위 큐	정렬된 데이터

 

시간복잡도 정리

 

연산	시간복잡도
삽입	O(log n)
삭제 (루트)	O(log n)
최대/최소 보기	O(1)
탐색 (특정 값)	O(n)

 

언어별 구현

 

 

Python

import heapq

# 최소 힙 (기본)
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)

print(heapq.heappop(heap))  # 1 (최소)

# 최대 힙 (음수로 변환)
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
print(-heapq.heappop(max_heap))  # 3 (최대)

 

Java

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(3);
minHeap.offer(1);
System.out.println(minHeap.poll());  // 1

// 최대 힙
PriorityQueue<Integer> maxHeap = 
    new PriorityQueue<>(Collections.reverseOrder());

 

정리 - 암기용

 

힙:

• 완전 이진 트리
• 배열로 구현
• 부모 > 자식 (최대 힙) 또는 부모 < 자식 (최소 힙)

인덱스 규칙:

• 왼쪽 자식: 2i + 1
• 오른쪽 자식: 2i + 2
• 부모: (i - 1) / 2

특징:

• 최대/최소 O(1)
• 삽입/삭제 O(log n)
• 우선순위 큐로 사용

BST와 차이:

• BST: 정렬된 순서
• 힙: 최대/최소만 빠름