힙(Heap) 자료구조의 특징과 힙 정렬(Heap Sort)의 동작 원리를 설명해주세요.

힙(Heap)은 완전 이진 트리의 일종으로, '힙 속성'을 만족하는 자료구조입니다. 힙 속성은 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나(최대 힙), 항상 작거나(최소 힙) 같은 것을 의미합니다. 이러한 특징 덕분에 힙은 우선순위 큐를 구현하는 데 효과적입니다.

힙 정렬은 힙 자료구조를 이용한 정렬 알고리즘입니다. 먼저 주어진 데이터를 힙으로 만듭니다. 최대 힙의 경우, 루트 노드에는 항상 가장 큰 값이 위치하게 됩니다. 이 루트 노드와 힙의 마지막 노드를 교환하고, 힙의 크기를 줄인 후 다시 힙 속성을 만족하도록 조정하는 과정을 반복합니다. 이 과정을 통해 내림차순으로 정렬된 배열을 얻을 수 있습니다. 힙 정렬은 평균적으로 O(n log n)의 시간 복잡도를 가집니다.