힙은 완전 이진 트리로 높이는 log n이기 때문에 하나의 요소를 힙에 삽입하거나 삭제할 때 θ(log n)의 시간 복잡도를 갖는다.
힙 정렬 알고리즘에서는 n개의 요소로 힙에 삽입하여 힙을 구성한 뒤에 n개의 요소를 힙에서 삭제하므로 총 θ(n log n)의 시간 복잡도를 갖는다.
즉, n크기의 데이터에 대한 이진탐색 알고리즘의 시간복잡도는 다음과 같다.
T(n) = θ(n log n)
void heapify(int* data_arr, int data_size, int i) {
int largest = i;
int left_child = 2 * i +1 ;
int right_child = 2 * i +2;
if (left_child<data_size && data_arr[left_child]>data_arr[largest])
largest = left_child;
if (right_child<data_size && data_arr[right_child]>data_arr[largest])
largest = right_cild;
if (largest != i) {
swap(data_arr[i], data_arr[largest]);
heapify(data_arr, data_size, largest);
}
}
void build_heap(int* data_arr, int data_size) {
for(int i = data_size / 2-1; i >= 0; i--)
heapify(data_arr, data_size, i);
}
void heap_sort(int* data_arr, int data_size) {
build_heap(data_arr, data_size);
for (int i = data_size-1; i >= 0; i--) {
swap(&data_arr[0], &data_arr[i]);
heapify(data_arr, i, 0);
}
}
정렬별 장단점 및 시간 복잡도
완전이진트리(Complete Binary Tree)란? - 준수의_개발정리노트
자료구조 힙이란? - heejeong Kwon