힙 정렬(Heap)

Goal

      - Heap Sort 에 대해 설명할 수 있다.

      - Heap Sort 과정에 대해 설명할 수 있다.

      - Heap Sort를 구현할 수 있다.

      - Heap Sort의 시간 복잡도를 계산 할 수 있다.

---

1. Heap Sort Summary

 

      - 힙 트리 구조(Heap Tree Structure)를 이용하는 정렬방법

      - 최솟값과 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리  

      - 이진 트리에 대한 이해 필요(완전 이진 트리)

      - 최대힙  = '부모 노드'가 '자식 노드' 보다 큰 힙

      - 힙 생성 알고리즘 (Heapify Algorithm) 을 사용해야함

                        - 힙 생성 알고리즘 = 특정한 노드의 두 자식 중에서 더큰 자식과 자신의 위치를 바꾸는 알고리즘

 

---

2. Heap Sort Processing

 

    - 정렬할 N개의 원소로 최대 힙 구성

    - 최대 힙의 루트 노드(가장 큰 원소)와 마지막 원소 위치 교환

    - 새 루트 노드에 대해 최대 힙 구성

    - 원소 개수만큼 2와 3을 반복 수행

 

---

3. Heap Sort Coding

 

//heap 정렬 이진트리 완전 이진 트리 구조
#include <stdio.h>

int number = 10;
int heap[10] = { 1, 4, 5, 6, 10, 9, 7, 8, 3, 2};
int main(void)
{
	int i , temp, c, root;
	//전체 트리 구조를 최대 힙 구조로 바꾼다
	 
	for(i = 1; i < number; i++) // i가 0이면 root 값을 나타나게 됨으로 1부터 시작 
	{
		c = i; // root와 비교하기위해 1부터 시작 
		do{
			root = ( c - 1) / 2; // c = 1부터 이기때문에 root 는 0부터 시작 
			if(heap[root] < heap[c])
			{
				temp = heap[root];
				heap[root] = heap[c];
				heap[c] = temp;
 			}
 			c = root;
		}while( c != 0); //c가 0이 될때까지 반복 
	}
	//크기를 줄여가며 반복적으로 힙을 구성
	for(i = number -1; i >= 0; i--)
	{
		temp = heap[0];
		heap[0] = heap[i];
		heap[i] = temp;
		root = 0;
		c = 1;
		do{
			c = 2 * root + 1;  
			//자식 중에 더큰 값을 찾기
			if(heap[c] < heap[c+1] && c < i - 1)
			{
				c++;
			}
			//루트보다 자식이 더 크다면 교환
			if(heap[root] < heap[c] && c < i)
			{
				temp = heap[root];
				heap[root] = heap[c];
				heap[c] = temp;
			}
			root = c;		
		}while(c < i);
	}
	for(i = 0 ; i < number; i++)
	{
		printf("%d ", heap[i]);
	}
	return 0;
 }

---

4. Heap 정렬 시간 복잡도

 

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

            - 병합 정렬, 퀵 정렬 만큼 빠른 정렬 알고리즘