힙 정렬

 

힙 정렬은 힙 트리 구조를 이용하는 정렬 방법이다.

 

이진트리

먼저 이진트리란 모든 노드가 두개의 자식노드를 가지는 것을 말한다. 트리라는 말 처럼 가지가 뻗어있는 형태다.

 

완전 이진 트리란 루트 노드부터 시작해서 자식 노드가 왼쪽 자식 노드, 오른쪽 자식 노드로 차근차근 들어가는 구조의 이진트리이다.

 

힙

힙(Heap)이란 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리이다.

>

최대 힙: '부모 노드'가 '자식 노드'보다 큰 힙을 말한다.

 

힙 정렬을 하기 위해서는 정해진 데이터가 힙 구조를 가지도록 만들어야 한다.

 

힙 정렬을 수행하기 위해서는 힙 생성 알고리즘을 사용한다. 이는 특정한 '하나의 노드'에 대해서 수행하는 것이다. 또한 해당 하나의 노드를 제외하고는 최대 힙이 구성되어 있는 상태라고 가정을 한다는 특징이 있다. 특정한 하나의 노드에 대해 최대 힙 정렬을 수행해주면 전체 트리가 최대 힙 구조로 형성된다.

 

힙 생성 알고리즘

힙 생성 알고리즘은 특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이다. 또한 위치를 바꾼 뒤에도 여전히 자식이 존내하는 경우 자식 중에서 더 큰 자식과 자신의 위치를 바꾸어야 한다.

 

힙 생성 알고리즘의 시간 복잡도

한 번 자식 노드로 내려갈 때마다 노드의 갯수가 2배씩 증가한다는 점에서 O(log N)이다.

데이터의 갯수가 1024개라면 10번 정도만 내려가면 된다.

 

모든 노드에 힙 정렬을 하면 N*(logN)이다.

 

#include<bits/stdc++.h>
using namespace std;
int number = 9;
int heap[9] = {7,6,5,8,3,5,9,1,6}; 
int main()
{
	for(int i=1; i<number; i++){
		int c=i;
		do {
			int root = (c-1)/2;
			if(heap[root] < heap[c]){
				int temp = heap[root];
				heap[root] = heap[c];
				heap[c] = temp;
			}
			c = root;	
		}while(c!=0);
	}
	//크기를 줄여가며 반복적으로 힙을 구성  
	for(int i=number-1; i>=0; i--){
		int temp = heap[0];
		heap[0] = heap[i];
		heap[i] = temp;
		int root=0;
		int c=1;
		do {
			c=2*root+1;
			//자식 중에 더 큰 값을 찾기 
			if(heap[c] < heap[c+1] && c<i-1){
				c++;
			}
			//루트보다 자식이 더 크다면 교환
			if(heap[root] < heap[c] && c<i){
				int temp = heap[root];
				heap[0] = heap[c];
				heap[c] = temp;
			} 
			root = c;
		} while(c<i);
	}
	for(int i=0; i<number; i++)
		cout << heap[i] << ' ';
}