Heapify

Heapify

"힙 속성을 유지하도록 트리를 정리하는 과정"

• 최대 힙(Max Heap) → 부모 노드가 항상 자식보다 크거나 같아야 함
• 최소 힙(Min Heap) → 부모 노드가 항상 자식보다 작거나 같아야 함
• Heapify 과정이 있어야 힙이 유지되고, 힙 정렬이 가능함

---

Heapify의 역할

• 힙이 깨졌을 때(힙 속성이 위반될 때) 이를 복구하는 과정
• 최대 힙에서는 부모보다 큰 자식이 있으면 Swap → 힙 속성을 유지
• 최소 힙에서는 부모보다 작은 자식이 있으면 Swap → 힙 속성을 유지
• 완전 이진 트리(Complete Binary Tree) 형태를 유지하면서 실행

출처: https://www.lavivienpost.net/heapsort-gif/

---

Heapify의 시간복잡도

 

• 힙의 높이(트리 깊이)만큼 Swap이 필요 → O(log n)
• 완전 이진 트리 구조이므로 높이는 log n 수준으로 유지됨
• 따라서 Heapify의 시간복잡도는 O(log n)