CS - Data Structure - Heap (힙)

Heap(힙)은 최댓값 및 최솟값을 빠르게 찾아내기 위한 자료구조로 우선순위 큐(Priority Queue)를 구현하는데 사용됩니다.

 

Heap은 완전 이진 트리로 최대 두 개의 자식 노드를 가질 수 있습니다.

 

[ 완전 이진 트리 ]

 

완전 이진 트리는 이진 트리의 한 종류로 단말 노드(leaf node)를 제외한 모든 노드는 2개의 자식을 가지거나 왼쪽 자식만을 가져야만 합니다.

 

예로

 

값 40, 50, 30을 가지는 단말 노드 (leaf node)를 제외한 모든 노드는 2개의 자식 노드를 가지고 있으므로 위 트리는 완전 이진 트리 입니다.

 

 

 

반면에 위와 같은 트리에서 값 30을 가지는 노드는 오른쪽 자식 노드 밖에 없으므로 위 트리는 완전 이진 트리가 아닙니다.

 

힙에는 두 가지 종류가 있습니다.

 

1. Min heap

2. Max heap

 

 

Min heap : 부모 노드의 값이 자식 노드의 값들보다 작거나 같은 힙

Max heap : 부모 노드의 값이 자식 노드의 값들보다 크거나 같은 힙

 

[ 힙의 사용 ]

 

우선순위 큐(Priority Queue)를 구현하는데 사용됩니다.

 

가장 먼저들어온 데이터가 가장 먼저 나가는 자료구조인 큐(Queue)와는 달리 우선순위 큐(Priority Queue)는 가장 우선순위가 높은 데이터가 먼저 나가는 자료구조입니다.

 

[ 힙의 시간복잡도 ]

 

데이터를 알맞은 위치에 배치하기 위해 O(log N)의 시간복잡도가 걸립니다.

 

 

[ 힙의 구현 ]

 

• 배열로 구현 가능
• 쉬운 구현을 위해 인덱스 0은 사용하지 않는다
• 힙에서 부모 자식 노드간의 인덱스 관계
  • 왼쪽 자식 인덱스 = (부모 인덱스) * 2
  • 오른쪽 자식 인덱스 = (부모 인덱스) * 2 + 1
  • 부모의 인덱스 = (자식 인덱스 ) / 2

 

최소 힙 예시

 

[ 힙에 새로운 요소 삽입 ]

 

1. 새로운 노드를 힙의 마지막 노드에 추가

2. 힙의 성질을 만족할때까지 부모 노드와 비교

 

 

위 예시에 5를 삽입해보자

 

 

부모 노드 40 > 5 이므로 교환

 

 

 

부모 노드 20 > 5 이므로 교환

 

부모 노드 10 > 5 이므로 교환

 

---

[ 힙에 요소 제거 ]

 

1. 루트 노드 삭제

2. 마지막 노드를 루트 노드에 배치

3. 힙 재구성

 

 

예시

 

1. 루트 노드 제거

 

2. 마지막 노드를 루트 노드에 배치

 

3. 힙 재구성