[CE] Heap and Complete Binary Tree

1. Heap(힙)

완전 이진 트리(Complete Binary Tree) 형태를 가진 특수한 Tree Data Structure.

• Heap은 우선순위 큐(Priority Queue) 를 구현하는 데 자주 사용됨: k-d Tree의 개선버전 등등
• 특히 최대값 또는 최소값을 빠르게 찾는 데 매우 효율적: Max-Heap에서 최대값을 $O(1)$ 시간에 찾을 수 있음.
• Heap Sort를 이용하면 sorting에 $O(n \log n)$ 의 시간복잡도를 가짐.

 

Heap의 가장 큰 특징은
부모 노드와 자식 노드 간의
우선순위 관계를 항상 유지한다는 것

 

https://dsaint31.tistory.com/463

[CE] Tree vs. Graph

https://dsaint31.tistory.com/853

[CE] Queue

---

---

2. Heap의 종류

1. Max-Heap (최대 힙):

• 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같아야 함.
• 루트 노드에는 가장 큰 값이 위치하게됨.

2. Min-Heap (최소 힙):

• 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같아야 함.
• 루트 노드에는 가장 작은 값이 위치.

---

다음은 complete binary tree와 Min-Heap, Max-Heap의 예를 보여줌.

---

참고: Complete Binary Tree

Complete Binary Tree는 모든 레벨이 마지막 레벨을 제외하고 완전히 채워져 있는 Binary Tree를 가리킴.

• 마지막 레벨외의 경우 반드시 완전히 채워져야 함.
• 마지막 레벨은 완전히 채워질 수도 있고 일부만 채워질 수도 있으며,
• 모든 노드는 왼쪽에서 오른쪽으로 채워져야 함.

---

3. Heap 동작방식 (새로운 데이터 삽입 및 루트노드 제거)

삽입과 제거 모두 Heap의 depth에 비례함.

• Heap depth는 Complete Binary Tree의 특성상 $\log(n)$ 이므로
• 삽입 및 제거의 연산의 시간 복잡도는 $O(\log n)$임.
• 여기서 $n$은 node의 갯수

---

3-1. Heap에 값을 삽입하는 과정:

1. 노드 추가: 새로운 노드를 트리의 마지막에 추가합니다.
2. Up-Heap (heapify up):
   •  부모 노드와 비교하여 우선순위 조건을 위반할 경우, 부모 노드와 위치를 교환합니다.
   • 이 과정을 루트 노드까지 반복합니다.

---

3-2. Heap에서 값을 삭제하는 과정: 최대 최소에 해당하는 root node가 삭제됨.

1. 루트 노드 제거: 루트 노드를 제거한 후, 트리의 마지막 노드를 루트 위치로 이동합니다.
2. Down-Heap (heapify down):
   • 자식 노드와 비교하여 우선순위 조건을 위반할 경우, 자식 노드와 위치를 교환.
   • 이 과정을 리프 노드에 도달할 때까지 반복.

---

3-3. 동작방식 예

삽입

 

삭제

 

---

4.  Python에서의 구현물

Python 표준 라이브러리에는 Min-Heap을 지원하는 heapq 모듈이 포함되어 있음.

Max-Heap을 구현하려면, 값을 삽입할 때 음수로 변환하여 사용하면 됨.

# Min-Heap
import heapq

# 데이터 리스트
data = [7, 2, 5, 1, 9, 4]

# Min-Heap 생성
heap = []
for num in data:
    heapq.heappush(heap, num)

# 힙에서 값 추출 (작은 값부터)
while heap:
    print(heapq.heappop(heap))

# Max-Heap

import heapq

# Max-Heap 구현 (음수로 변환)
data = [7, 2, 5, 1, 9, 4]
max_heap = []
for num in data:
    heapq.heappush(max_heap, -num)

# Max-Heap에서 값 추출 (큰 값부터)
while max_heap:
    print(-heapq.heappop(max_heap))

---