힙 정렬(Heap Sort)

힙 정렬이란? 힙 트리 구조를 이용하는 정렬 방법

 

힙 정렬 선행 지식: 힙 < 이진트리 < 완전이진트리

 

이진트리란? 한 노드의 자식 노드가 최대 2개인 자료구조

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

 

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

--> EX) 최대 힙(Max Heap), 최소 힙(Min Heap)

완전 이진트리를 표현하기 위해 배열을 사용해도 된다. 배열에서 데이터와 Index 관계가 매우 중요하다

 

먼저, 힙 정렬을 수행하기 위해서는 힙 생성 알고리즘을 사용 

힙 생성 알고리즘의 시간 복잡도는 O(log N)

 

트리를 힙 구조로 변환하는 시간 복잡도는 O(N) 데이터 갯수 만큼만 연산이 필요

Idea. 0번 Index의 값은 제일 커야한다. --> 최대 힙의 특성 : 루트 노드의 데이터가 제일 크다.

 

힙 구조에서 정렬

Idea. 힙 구조에서는 Root 노드의 데이터는 제일 크다. 반대로 Leaf 노드의 데이터는 제일 작을 것이다.
--> Root 노드의 데이터와 Leaf 노드의 데이터를 비교하며 교환함.

--> 추가로, 해당 Root 노드의 데이터와 자식 노드를 비교해 큰 값과 교환

 

#include <iostream>
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);
	}

	// 힙 정렬 시작
	// Idea. 최대 힙으로서, 루트는 항상 최대를 뜻함. 그래서 leaf와 root노드와 교체하는 방식
	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[root] = heap[c];
				heap[c] = temp;
			}
			root = c;
		} while (c < i);
	}


	for (int i = 0; i < number; i++)
	{
		printf("%d ", heap[i]);
	}
}

 

 

힙 정렬의 전체 시간 복잡도는 O(N * Log N) -> 트리의 높이를 이용한 것이기 때문에 잘 생각 해보세요

그리고 힙 정렬의 장점은 병합 정렬과 다르게 별도로 추가적인 배열이 필요하지 않다는 점에서 메모리 측면에서 효율적!