[정렬] 힙 정렬 (Heap Sort )

void heapify(vector<int>& v, int size, int i) {
	int c = 2 * i + 1; // 왼쪽자식 선택
	if (c < size - 1 && v[c] < v[c + 1]) c++; //오른쪽자식 존재하면서, 오른쪽자식이 더크면 오른쪽 자식 선택
	if (c < size && v[i] < v[c]) swap(v[i], v[c]); // 부모보다 자식이 더크면 둘이 바꿈
	if (c < size / 2) heapify(v, size, c); //내부노드에서 한정하여 반복
}

void heapSort(vector<int>& v, int size) {
	for (int i = size / 2;i >= 0;i--) {
		heapify(v, size, i);
	}
	for (int i = size - 1;i >= 0;i--) {
		swap(v[i], v[0]);//힙이 만들어지고 맨처음값과 맨 뒷 값 변경
		heapify(v, i, 0);// 사이즈 조절 후 
	}
}

제자리성 : 제자리 정렬

 

시간복잡도

최악시간 복잡도 = O(nlogn) (완전 이진트리)

 

알고리즘

1. 전체 이진트리로 만들기

2. 서브트리마다 최대 힙구조로 만들기

3. 맨 첫번째 원소와 마지막 원소를 스왑

4. 위의 과정 반복