🔍 힙 정렬 알고리즘이란?

힙 정렬 알고리즘(Heap Sort)이란 배열을 트리 형태인 힙(heap) 구조로 만든 후, 힙의 특성을 활용해 정렬하는 알고리즘입니다

🛠️ 힙 정렬의 시간복잡도

시간 복잡도 힙 정렬의 시간 복잡도는 최선/평균/최악/의 경우 모두 O(n log n)입니다

힙을 구성하는 데 O(n), 정렬하는 데 O(n log n)이 필요하기 때문입니다

🛠️ 힙 정렬의 공간복잡도

힙 정렬의 공간 복잡도는 일반적으로 O(1)입니다

📌장점

• 항상 O(n log n)의 성능을 보장합니다
• 안정성이 뛰어나 많은 데이터 처리에 적합합니다
• in-place 정렬이므로 추가적인 메모리 사용이 없습니다

📌단점

• 불안정 정렬이라, 원본 순서를 보장하지 않습니다
• 시간복잡도는 동일하나 퀵정렬보다 느립니다

✍️결론

힙 정렬은 배열을 트리 형태인 힙(heap) 구조로 만든 후, 힙의 특성을 활용해 정렬하는 알고리즘입니다

항상 O(n log n)의 성능을 보장하기 때문에, 일정하고 빠르게 정렬할 수 있다는 장점이 있지만,
배열을 트리형태인 힙 구조로 바꾸는 과정떄문에, 다른 정렬에 비해 구현이 복잡하다는 단점이 있습니다