힙 정렬(Heap Sort)

힙 정렬

힙 정렬(Heap Sort)은 완전 이진 트리인 힙을 이용해서 원소들의 최댓값이나 최솟값을 쉽게 찾고 그것을 이용해서 정렬하는 알고리즘입니다.

먼저 부모 노드의 값이 자식 노드의 값보다 큰 최대 힙 구조를 만들어줍니다.

그리고 가장 큰 값을 가지고 있는 루트 노드를 힙의 마지막 노드와 교환해 주고 다시 최대 힙 구조를 만들어줍니다. 이 과정을 원소의 수 - 1번 반복하면 정렬이 완료됩니다.

 

힙 정렬 예시

본격적인 힙 정렬을 하기 전에 부모 노드의 값이 자식 노드의 값보다 큰 최대 힙 구조를 만들어야 합니다.

힙은 1차원 배열을 이용해서 구현할 수 있습니다.

부모 노드와 자식 노드의 인덱스를 쉽게 구하기 위해서 배열의 0번째 공간은 사용하지 않고 1번째 공간부터 사용합니다.

부모 노드 인덱스 -> 자식 노드 인덱스 / 2

왼쪽 자식 노드 인덱스 -> 부모 노드 인덱스 * 2

왼쪽 자식 노드 인덱스 -> 부모 노드 인덱스 * 2 + 1

부모 노드의 값을 구하고 값이 자신의 값보다 작으면 둘을 교환합니다.

 

최대 힙이 완성되었다면 본격적인 힙 정렬을 시작합니다.

가장 큰 값을 가지고 있으면서 트리의 최상단에 위치한 루트 노드와 가장 마지막 노드를 교환합니다.

원래 부모 노드는 자식 노드보다 큰 값을 가지고 있어야 하는데 루트 노드와 가장 마지막 노드를 교환하면서 루트 노드는 자식 노드보다 큰 값을 가졌다고 할 수 없게 되었습니다.

따라서 루트 노드와 두 자식 노드 중 더 값이 큰 노드와 교환해줍니다.

이 과정을 교환된 노드에서 반복해줍니다.

위의 모든 과정을 원소의 개수 - 1번만큼 반복해줍니다.

 

힙 정렬 C++ 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>

void BuildHeap(int number, int numbers[]);
void Heapify(int number, int numbers[], int index);
void HeapSort(int number, int numbers[]);
void Swap(int* a, int* b);

int main()
{
	int number;
	int numbers[1000];

	memset(numbers, 0, sizeof(numbers));

	scanf("%d", &number);

	for (int i = 1; i <= number; i++)
	{
		scanf("%d", &numbers[i]);
	}

	HeapSort(number, numbers);

	for (int i = 1; i <= number; i++)
	{
		printf("%d\n", numbers[i]);
	}
}

void HeapSort(int number, int numbers[])
{
	BuildHeap(number, numbers);

	for (int i = number; i > 1; i--)
	{
		Swap(&numbers[1], &numbers[i]);
		Heapify(i - 1, numbers, 1);
	}
}

void BuildHeap(int number, int numbers[])
{
	for (int i = 2; i <= number; i++)
	{
		while (i > 1)
		{
			int parent_node = i / 2;

			if (numbers[i] > numbers[parent_node])
			{
				Swap(&numbers[i], &numbers[parent_node]);
				i = parent_node;
			}
			else
				break;
		}
	}
}

void Heapify(int number, int numbers[], int index)
{
	if (index == 0)
		return;

	int current_node = index;
	int left_child_node = index * 2;
	int right_child_node = index * 2 + 1;

	if (left_child_node <= number && numbers[current_node] < numbers[left_child_node])
	{
		current_node = index * 2;
	}

	if (right_child_node <= number && numbers[current_node] < numbers[right_child_node])
	{
		current_node = index * 2 + 1;
	}

	if (current_node != index)
	{
		Swap(&numbers[index], &numbers[current_node]);
		Heapify(number, numbers, current_node);
	}
}

void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

 

힙 정렬 시간복잡도

최선	평균	최악
nlog2n	nlog2n	nlog2n