[C++] 힙정렬 (Heap sort) 개념 및 구현

특징

1. 동일한 원소 존재시, 원래의 순서를 보존하지 않는 불안정 정렬

3. 일반적으로 최고, 평균, 최악 시간 복잡도O(N * logN)

4. 추가 버퍼가 필요하지 않으므로 공간 복잡도 O(1)

 

 

알고리즘

힙(Heap) 자료구조를 이용하여 정렬한다.

 

힙은 마지막 depth를 제외하고 모든 노드가 왼쪽부터 채워져있는 완전 이진 트리 구조이며,

제일 큰 수나, 제일 작은 수를 빠르게 뽑아낼 수 있도록 하는 자료구조다.

 

최대힙은 트리의 노드 중 최댓값이 루트 노드에 존재하며,

최소힙은 트리의 노드 중 최솟값이 루트 노드에 존재한다.

 

힙정렬은 최대힙과 최소힙으로 모두 구현 가능하지만, 본 포스팅은 최대힙으로 진행한다.

 

 

 

완전 이진트리는 위와 같이 배열로 표현할 수 있다.

혹은 배열을 위와 같은 완전 이진 트리로 볼 수도 있다.

 

입력 버퍼는 배열이기 때문에 완전 이진 트리로 본다면,

특정 노드의 왼쪽 자식은 index * 2 + 1, 오른쪽 자식은 index * 2 + 2로 구할 수 있고,

특정 노드의 부모는 (index - 1) / 2로 구할 수 있다.

 

ex) index가 0인 요소 3의 왼쪽 자식은 0 * 2 + 1로 index가 1이고, 오른쪽 자식은 0 * 2 + 2로 index가 2다.

      index가 4인 요소 1의 부모는 (4 - 1) / 2로 1.5이고, 내림하면 index가 1로 구해진다.

 

 

 

먼저 입력 버퍼를 받은 이후, Heapify 라는 힙 생성 알고리즘을 수행해야한다.

 

Heapify의 핵심은 부모와 자식 노드를 비교해 더 큰 값(최대 힙일 경우)을 부모로 옮기는 것이다.

 

위의 그림에서 부모인 3과 자식인 4를 비교했을 때, 자식이 더 크기 때문에 swap을 진행한다.

 

 

이러한 Heapify 알고리즘은 자식을 가진 모든 부모를 대상으로 진행한다. (혹은 부모를 가진 모든 자식을 대상으로) O(log N)

 

위의 그림에서 2와 7의 swap이 진행된 이후,

바뀐 7의 부모인 4와도 최대힙 구조가 맞춰져있지 않기 때문에 루트 노드까지 비교 및 swap을 진행해야 한다.

 

 

마찬가지로 오른쪽 서브트리도 진행해준다. 이번에는 6과 7에 대해서 최대힙 구조가 만족하므로 swap하지 않는다.

 

 

Heapify가 수행되면 위와 같이 우선순위가 높은 원소가 루트 노드로 이동하게 된다.

 

여기까지가 Heap이고, 아래부터는 이를 이용한 힙 정렬을 설명한다.

 

 

최댓값을 찾았으므로 이를 제일 오른쪽 아래 (마지막 인덱스) 노드와 swap 한다.

 

그럼 맨 마지막 요소는 정렬이 완료된 상태가 된다.

 

하지만 swap을 한 탓에 힙 구조가 붕괴된 것을 볼 수 있다.

 

정렬이 완료된 7은 제외해야 하므로, Size를 1 줄여 다시 Heapify를 진행한다.

 

 

다시 한 번 Heapify를 진행하면 아래와 같이 또 최대힙 구조가 완성되고,

 

또 다시 루트와 7 제외 마지막 index를 swap한다.

 

 

이를 n-1번 반복하면 정렬이 완료된다. O(N)

 

Heapify (O(log N)) * n-1번 반복 (O(N)) =  O(N * log N)

 

 

구현 및 상세 설명

static void swap(int& first, int& second)
{
	int temp = first;
	first = second;
	second = temp;
}

void sort(std::vector<int>& buf)
{
	heapify(buf);

	for (int i=(int)buf.size()-1; i>=0; --i)
	{
		swap(buf[0], buf[i]);
		re_heapify(buf, i);
	}
}

 

먼저 전체적인 로직은 들어온 입력 버퍼에 대해 heapify를 수행하고

구해진 최댓값을 맨 뒤의 원소와 swap하고 다시 heapify를 진행한다. (n-1번 반복)

 

static void heapify(std::vector<int>& buf)
{
	for (int i=1; i<(int)buf.size(); ++i)
	{
		int cur = i;
		while (cur > 0)
		{
			int parent = (cur - 1) / 2;

			if (buf[parent] < buf[cur])
				swap(buf[parent], buf[cur]);
			cur = parent;
		}
	}
}

 

heapify()의 구현은 이렇다.

 

부모의 입장에서 자식과 비교한다면 buffer overflow를 많이 고려해야 하므로, 자식의 입장에서 부모와 비교했다.

 

0번 index는 루트 노드라 부모가 없기에 1부터 진행한다.

 

parent의 index를 구해주고 비교하여 swap한다.

 

이후 새롭게 바뀐 부모 노드와 그 노드의 부모 노드도 비교 해주어야 Heap 구조가 유지된다.

이를 while 문에서 반복하며, 계속 상위 노드로 올라가 비교하고, 자신이 루트 노드가 된다면 중단한다.

 

static void re_heapify(std::vector<int>& buf, int max)
{
	int parent = 0;

	while (true)
	{
		int cur = 2*parent+1;
		if (cur >= max)
			break;
		if (cur+1 < max && buf[cur+1] > buf[cur])
			cur = cur+1;
		if (buf[parent] < buf[cur])
			swap(buf[parent], buf[cur]);
		parent = cur;
	}
}

 

최대힙이 완성되고 마지막 요소와 swap된 이후 re_heapify()가 호출되는데

이는 바뀐 루트 노드로부터 두 자식을 비교해 더 큰 쪽과 바꾸고, 바꾼 서브트리로만 내려가며 Heapify를 진행한다.

자식들 중 더 작은 노드는 건들지 않았기 때문에 그 서브트리는 볼 필요가 없기에 최적화한다.

 

 

테스트

#include <vector>
#include <iostream>
#include <cstdlib>
#include "HeapSort.hpp"

static void sortChecker(std::vector<int>& buf)
{
	for (int i=0; i<(int)buf.size()-1; ++i)
	{
		if (buf[i] > buf[i+1])
		{
			std::cout << "\e[31mX\e[0m ";
			return;
		}
	}
	std::cout << "\e[32mV\e[0m ";
}

int main(int ac, char** av)
{
	if (ac < 2)
	{
		std::cout << "<Usage> : ./a.out 5 2 4 1 3\n";
		return 1;
	}

	std::vector<int> buf;
	buf.reserve(ac);

	for (int i=1; i<ac; ++i)
		buf.push_back(atoi(av[i]));

	heap::sort(buf);
	
	sortChecker(buf);
	return 0;
}

#!/bin/bash

# Linux
echo -n "1. Positive test : "
$1 `seq 0 0 | shuf | tr "\n" " "`
$1 `seq 0 2 | shuf | tr "\n" " "`
$1 `seq 1 100 | shuf | tr "\n" " "`
$1 `seq 1 100000 | shuf | tr "\n" " "`
$1 `seq 2147480000 2147483647 | shuf | tr "\n" " "`
for _ in {1..50}; do
	$1 `shuf -i 1-10000000 -n 1000 | tr "\n" " "`
done
echo ""

echo -n "2. Negative test : "
$1 `seq -1 -1 | shuf | tr "\n" " "`
$1 `seq -2 0 | shuf | tr "\n" " "`
$1 `seq -100 -1 | shuf | tr "\n" " "`
$1 `seq -99999 -1 | shuf | tr "\n" " "`
$1 `seq -2147483648 -2147473648 | shuf | tr "\n" " "`
for _ in {1..50}; do
	$1 `shuf -i 1-10000000 -n 1000 | tr "\n" "_" | sed 's/_/ -/g'`
done
echo ""

echo -n "3. Integer test : "
$1 `seq -1 1 | shuf | tr "\n" " "`
$1 `seq -3 2 | shuf | tr "\n" " "`
$1 `seq -100 100 | shuf | tr "\n" " "`
$1 `seq -33121 32451 | shuf | tr "\n" " "`
$1 `seq -3 123123 | shuf | tr "\n" " "`
$1 `seq -112312 6 | shuf | tr "\n" " "`
for _ in {1..50}; do
	$1 `shuf -i 1-10000000 -n 1000 | tr "\n" " "` `shuf -i 1-10000000 -n 1000 | tr "\n" "_" | sed 's/_/ -/g'`
done
echo ""

결과

 

전체 코드

https://github.com/SikPang/Algorithms/tree/main/HeapSort

 

 

참고 자료

https://www.youtube.com/watch?v=iyl9bfp_8ag&t=790s

 

개인 공부용 포스팅인 점을 참고하시고, 잘못된 부분이 있다면 댓글로 남겨주시면 감사드리겠습니다.