목록2025/02/19 (1)

데이터 분석 기술 블로그

Heapify

Heapify"힙 속성을 유지하도록 트리를 정리하는 과정"최대 힙(Max Heap) → 부모 노드가 항상 자식보다 크거나 같아야 함최소 힙(Min Heap) → 부모 노드가 항상 자식보다 작거나 같아야 함Heapify 과정이 있어야 힙이 유지되고, 힙 정렬이 가능함Heapify의 역할힙이 깨졌을 때(힙 속성이 위반될 때) 이를 복구하는 과정최대 힙에서는 부모보다 큰 자식이 있으면 Swap → 힙 속성을 유지최소 힙에서는 부모보다 작은 자식이 있으면 Swap → 힙 속성을 유지완전 이진 트리(Complete Binary Tree) 형태를 유지하면서 실행Heapify의 시간복잡도 힙의 높이(트리 깊이)만큼 Swap이 필요 → O(log n)완전 이진 트리 구조이므로 높이는 log n 수준으로 유지됨따라서 H..
데이터 사이언스/알고리즘 2025. 2. 19. 13:50
이전 Prev 1 Next 다음