힙 정렬 (Heap Sort) (C++)

힙 정렬 (Heap Sort)힙 정렬은 힙(Heap) 자료구조를 이용한 정렬 알고리즘으로, 완전 이진 트리의 특성을 활용하여 데이터를 정렬. 힙 정렬은 선택 정렬의 확장으로 볼 수 있으며, 데이터를 효율적으로 정렬하기 위해 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 사용.동작 원리힙 생성 (Heapify):주어진 배열을 최대 힙(부모가 자식보다 크거나 같음) 또는 최소 힙(부모가 자식보다 작거나 같음)으로 변환.정렬:힙의 루트(최댓값 또는 최솟값)를 배열의 끝으로 이동하고, 힙 크기를 줄인다.줄어든 힙에 대해 다시 힙 구조를 유지하도록 정렬(Heapify).이 과정을 힙 크기가 1이 될 때까지 반복.특징시간 복잡도:최선/평균/최악: O(nlog⁡n)힙 구성: O(n), 삭제 및 정렬: ..

2025.01.04