[알고리즘] 힙 정렬 (heap sort)

힙정렬

힙정렬은 힙 자료구조를 이용하는 정렬 알고리즘.

힙 : 힙 조건을 만족하는 완전 이진트리. (힙 조건 -최대힙- 각 노드의 값이 자식 노드의 값보다 커야 한다는 것)

n개의 노드를 가진 힙의 높이 = log2 n

힙의 루트에는 가장 큰 수가 저장되므로, 루트의 숫자를 힙의 가장 마지막 노드에 있는 숫자와 바꿈. 즉, 가장 큰 수를 배열의 가장 끝으로 이동시킨 것. 그리고 힙의 크기를 1 줄인후, 루트에 새로 저장된 숫자로 인해 위배된 힙 조건을 해결하여 새로운 루트의 숫자를 힙의 마지막 노드에 있는 숫자와 바꿈. 이를 반복.

수도코드 및 시간복잡도

힙 정렬

입력:입력이 A[1]부터 A[n]까지 저장된 배열A
출력:정렬된 배열 A
배열 A의 숫자에 대해서 힙 자료 구조를 만든다
heapSize = n //힙의 크기를 조절하는 변수
for i=1 to n-1
	A[1] <-> A[heapSize] //루트와 힙의 마지막 노드를 교환
	heapSize -= 1 //힙의 크기 1 감소
	DownHeap() //위배된 힙 조건 만족
return A

힙을 만들기(===== DownHeap) => O(n)

BuildHeap(A)
{
for (i = [n/2] to 1) //[n/2] = 버림
	DownHeap(i)
}

DownHeap(i)
leftChild = 2i //i의 왼쪽 자식 노드
rightChild = 2i + 1 //i의 오른쪽 자식 노드
if ((leftChild <= n) and (A[leftChild] > A[i]))
	bigger = leftChild
else
	bigger = i
if ((rightChild <= n) and (A[rightChild] > A[bigger]))
	bigger = rightChild
if (bigger != i)
{
 	A[i] <-> A[bigger]
    DownHeap(bigger)
}

시간복잡도 : 힙을 만들때 높이 h에서 어느 정도의 시간이 걸리는지 알아야 시간 복잡도 판단이 가능하다. 주어진 배열의 크기가 n일때 높이가 h인 트리는 "n/2^(h+1) 의 올림"만큼 나오고, downheap에 대한 시간은 O(1)상수시간이므로, 이를 잎노드의 부모까지 도달할 때까지 하므로, h를 곱해주면 된다.

노드 삭제 ,  노드 삽입

"노드 삭제"의 최악의 경우, 힙의 마지막 노드의 숫자가 힙의 이파리 노드에 저장되는 경우이므로 힙의 높이만큼 downheap을 반복하기 때문에 O(log n)이 걸린다.

"노드 삽입"의 최악의 경우, 새로 저장되는 값이 힙의 루트에 저장될 때이고, 힙의 높이만큼 downheap을 반복하기 때문에 O(log n)이 걸린다.

---

힙 정렬의 전체 시간복잡도>

힙 만드는데  : O(n)

for 루프 n-1 번 수행 되므로  : n-1번

downheap은 최악의 경우 이파리 노드까지 내려가며 교환할때이므로, 힙의 높이가 log2 n을 넘지 않기 때문에 :  O(log n)

=> O(n) + (n-1) x O(log n) = O(nlog n) 

코드(c)

(완벽x 수정중)

/*
입력:입력이 A[1]부터 A[n]까지 저장된 배열A
출력:정렬된 배열 A
배열 A의 숫자에 대해서 힙 자료 구조를 만든다
heapSize = n //힙의 크기를 조절하는 변수
for i=1 to n-1
	A[1] <-> A[heapSize] //루트와 힙의 마지막 노드를 교환
	heapSize -= 1 //힙의 크기 1 감소
	DownHeap() //위배된 힙 조건 만족
return A
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int N;
void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void downheap(int m[], int k,int nn)
{
	int leftChild = 2 * k;
	int rightChild = 2 * k + 1;
	int bigger;

	if ((leftChild <= nn) && (m[leftChild] > m[k]))
		bigger = leftChild;
	else
		bigger = k;
	if ((rightChild <= nn) && (m[rightChild] > m[bigger]))
		bigger = rightChild;
	if (bigger != k)
	{
		swap(&m[k], &m[bigger]);
		downheap(m,bigger , nn);
	}
}
void buildHeap(int m[], int n)
{
	for (int i = n / 2; i >= 1; i--)
	{
		downheap(m,i,n);
	}
}
int main() {
	//입력 받기
	scanf("%d", &N);
	int* m = (int*)malloc(sizeof(int) * (N+1));
	m[0] = 9999;//힙 정렬은 인덱스 1부터 쓰므로, 쓰레기값 넣기
	for (int i = 1; i < N+1; i++)
		scanf("%d", &m[i]);

	//초기 힙 구성
	buildHeap(m, N);
	//힙 정렬 수행
	for (int i =N ; i>= 2 ; i--)
	{
		swap(&m[1], &m[i]);
		downheap(m, 1, i - 1);
	}
	//결과 출력
	for (int i = 1; i < N+1; i++)
	{
		printf("%d ", m[i]);
	}
	return 0;
}

BOJ