Heap Sort(힙 정렬)

Heap Sort는 고급 프로그래밍 기법에서도 자주 사용될 정도로 중요한 알고리즘에 속한다. Heap Sort는 Heap tree structure를 사용하는 정렬방법이다.
Heap은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 사용하는데, 최대힙은 부모 노드가 자식 노드보다 큰 힙이라고 할 수 있다.
힙 정렬에서는 Heapify algorithm이라는 부모와 두 자식노드를 비교하여 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이다. 이것을 최하단 노드까지 비교하게 됩니다.

Heap Sort는 Heapify algorithm의 속도가 log n 전체 데이터 갯수가 n개이므로 O(N*logN)의 시간복잡도를 가지게 됩니다.

Heap Sort Code

#include<iostream>

void heapify(int data[], int n, int i)
{
    int largest = i; 
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    
    if (l < n && data[l] > data[largest])
        largest = l;
 

    if (r < n && data[r] > data[largest])
        largest = r;
 

    if (largest != i) {
        std::swap(data[i], data[largest]);


        heapify(data, n, largest);
    }
}
 
 
void heapSort(int data[], int n)
{
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(data, n, i);
 
    for (int i = n - 1; i > 0; i--) 
	{
    	
        std::swap(data[0], data[i]);
 
        heapify(data, i, 0);
    }
}


void printData(int data[], int n)
{
    for (int i = 0; i < n; ++i)
        std::cout << data[i] << " ";
}

int main()
{
	int data[] = {5, 8, 2, 7, 4, 1, 9, 6, 3};
	int number = sizeof(data) / sizeof(data[0]);
	
	heapSort(data, number);
	
	printData(data, number);
	
	return 0;

}

이미지 출처
자료 출처
자료 출처2