개요

힙 정렬이란 이진 트리인
maxheap,minheap 트리를 사용하는 정렬의 종류다.

heap이란
완전 이진트리를 기본으로 한 자료구조로
두가지 형태가 있다.

• 부모 노드의 키값이 자식 노드보다 항상 큰 힙을
  최대힙이라 부르고,
• 부모 노드의 키값이 자식 노드보다 항상 작은 힙을
  최소힙이라 부른다.

이 중 최대힙트리를 이용했다.

배열에서 parent노드 위치는 child노드 위치 /2인 점과,
child노드의 위치는 parent노드/2, parent노드/2+1인 점을
활용하여 구현했다.

1. 배열을 최대힙으로 구현을 한다. (buildHeap()함수부분)
   단 구현할 때, 힙 root위치를 0으로 하면
   child가 다 0이 되어버려서
   힙의 root위치는 0이 아니라 1이다.
   따라서, 0을 미리 넣은 벡터에 해당 배열을 복사하고
   해당 벡터를 최대힙으로 만들었다.

2. 최대힙의 root 위치에 있는 제일 큰 값을
   마지막 값과 교환한다.

3. 제일 큰 값이 맨 뒤로 빠졌으므로 큰값이 정렬되었다.
   따라서, 맨 뒤에 값을 제외한 나머지 범위에서
   다시 최대힙을 만든다. (heapify()함수 부분)

4. 2~3단계를 반복하면 벡터가 정렬이 되고,
   해당 벡터를 원래 배열에 복사해준다.

구현

#include<iostream>
#include<vector>
using namespace std;

int arr[8] = { 9,6,7,5,3,1,4,2 };							//처음 노드를 1로 해야하는데, 어캐해야하지.
															// 0을 미리넣은 vector 생성 및 arr값 복사해서 넣어준후 마지막에 arr값에 정렬된값 복사하자
vector<int> v;

void buildHeap(int* arr, int* end) {						//일단 maxheap의 형태로 만들자.
	int root = 1,parent=1,child=1;
	v.push_back(0);
	for (int i = 0; i < end - arr; i++) {
		v.push_back(arr[i]);
	}
	for (int i = end-arr-1; i >1; i--) {
		child = i;
		parent = child/2;
		while (v[child]> v[parent] && parent!=0) {
			swap(v[child], v[parent]);
			child = parent;
			parent = child / 2;
		}
	}
}

void heapify(int start, int end) {							//start(거의 1)에서 end범위에서 heap을 만들어준다. 제일 큰값이 1의 위치로 오게
	int current = start;									//current커서에 start값 넣어줌
	int leftchild = 2 * current;							//leftchild에 2*current
	int rightchild = 2 * current+1;							//rightchild에 2*current+1

	if (leftchild<=end && v[current ]< v[leftchild]) current = leftchild;		//leftchild 노드값이 end값 넘는 지 체크, current값이 leftchild값보다 작으면 current 커서 옮겨줌
	if (rightchild<=end && v[current] < v[rightchild]) current = rightchild;	//rightchild 노드값이 end값 넘는 지 체크, current값이 rightchild값보다 작으면 current 커서 옮겨줌

	if (start != current) {														//current커서가 움직였다면 parent노드보다 큰 child노드 하나 있는것이므로
		swap(v[start], v[current]);												//해당 current노드 값과 start노드 값 바꿔주고
		heapify(current, end);													//해당 current노드에서부터 다시 heapify시작
	}



}

void heapSort(int*arr,int*end) {
	buildHeap(arr, end);									//max힙의 형태로 만든후
	for (int i = end - arr ; i > 1; i--) {					//맨 마지막 원소부터 2번째 원소까지  
															
		swap(v[1], v[i]);									//i번째 원소와 제일큰원소 바꾼 후,
		heapify(1,i-1);										//제일 큰원소는 정렬 되어 있으므로 정렬된값 제외하고 다시 maxheap으로 만들어주고 반복
	}
	for (int i = 0; i < v.size()-1; i++) {					//정렬된 v값 넣어주기
		arr[i] = v[i + 1];
	}
}

void print() {
	for (int elem : arr) {
		cout << elem << " ";
	}
}


int main() {
	heapSort(arr, arr + 8);
	print();
}