4. 힙 정렬 heap sort

2751. 수 정렬하기 2

https://www.acmicpc.net/problem/2751

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1<=N<=1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절대값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 

5
5
4
3
2
1

예제 출력 

1
2
3
4
5

1. 힙 정렬 heap sort 소개

O(n * log n)의 시간복잡도를 가지는 또 다른 정렬 알고리즘을 알아보자 

힙 정렬은 말 그래도 힙 자료구조를 사용한 정렬방법이다.

따라서 이해하기 위해선 힙이 무엇인지부터 알아야 한다!

1-1) 힙 자료구조 소개

우선 힙은 완전이진트리다. 

이진트리라 함은 한 노드가 최대 두 개의 자식노드를 가진다는 뜻이고,

완전이진트리라 함은 마지막 level = depth 를 제외하고 모든 레벨은 노드가 가득 차있으며, 마지막 레벨은 노드가 왼쪽부터 채워져 있다는 뜻이다.

힙의 강점은 부모-자식 간에 대소관계가 전부 적용되어 있다는 것이다. 단 형제들 끼리는 적용하지 않는다.

(최대힙이라면) 따라서 루트노드는 가장 큰 노드가 될 것이다.

따라서 이러한 힙(최대 힙)을 유지한다면 O(1)에 가장 큰 수를 찾을 수 있다.

우선순위 큐도 비슷한 자료구조로 구현되어 있다고 한다.

1-2) 힙 자료구조 구성하기

힙은 트리로 되어있지만, 완전이진트리라는 점에서 배열로 구현할 수 있다.

루트노드를 인덱스 0으로 잡을시, 부모 노드의 인덱스가 x라면, 왼쪽 자식의 인덱스는 (x * 2 + 1),

오른쪽 자식의 인덱스는 (x * 2 + 2) 이다.

루트노드를 인덱스 1으로 잡을시, 부모 노드의 인덱스가 x라면, 왼쪽 자식의 인덱스는 x * 2, 

오른쪽 자식의 인덱스는 (x * 2 + 1) 이다.

이제 전체 배열을 힙으로 만들어 보자!

힙으로 만드는데는 부모노드를 조지는 방법이 효과적이다.

간단히 노드 세 개의 이진트리를 생각해보면,

루트 노드가 3이고, 두 자식 노드가 모두 3보다 크다면 어찌되었건 부모 노드를 아무 자식과 스왑해주면 끝이다.

그래서 작은 부분 부분 힙을 만들어주면서 확장시키는 방법을 쓴다.

코드로 보면 이해가 빠르당

void down_heap(int x, int size) {
    int left, right, p;
    while (x < size) {
        left = x * 2 + 1;
        right = x * 2 + 2;
 
        if (left >= size && right >= size)
            break;
 
        p = x;
        if (left < size && arr1[p] < arr1[left])
            p = left;
        if (right < size && arr1[p] < arr1[right])
            p = right;
        if (p == x)
            break;
 
        int tmp = arr1[x];
        arr1[x] = arr1[p];
        arr1[p] = tmp;
 
        x = p;
    }
}

x를 부모 노드로 잡고 힙이 될 조건(부모가 제일 큼)을 만족할 때 까지 밑으로 조져버린다.

함수를 배열 맨 뒤에서 부터 호출해주면 되는데,

시간을 절약하기 위해선 리프 노드에 대해선 호출할 필요가 없다는 점을 기억하자.

1-3) 힙 정렬하기

이제 힙을 완성했으니 정렬에 써먹어 보자.

힙의 장점 : 최대값을 O(1)에 알 수 있다 / 를 활용하는 것이다.

오름차순이라면 배열의 최대값은 배열 맨 뒤에 있어야 한다. O(1)에 알 수 있다. 힙에서 베껴온다.

그럼 그 다음으로 큰 수는 어떻게 알 수 있을까? 

일단 다음으로 큰 수는 루트(부모)의 두 자식 중에 한 놈이다.

하지만 우리의 목표는 계속 힙 구조를 유지하면서 장점을 써먹는 것이므로, 루트를 잃어버린 힙을 재구성해야 한다.

재구성은 간단하다. 위에서 했던 down_heap()을 활용한다.

루트를 힙의 누군가로 새롭게 대체하고 밑으로 조져버리면, 루트의 두 자식 중에 큰 놈이 위로 올라올 것이고, 대체자는 본연의 자리를 찾아갈 것이므로 힙이 새롭게 재구성되는 것이다.

루트를 새로 채울 놈은 누구를 써야 하는가? 만만한건 제일 마지막에 있는 리프 노드다.

그림으로 확인해보자.

2. 코드

#include <stdio.h>
#include <vector>
using namespace std;
 
int n;
vector<int> arr1, arr2;
 
void down_heap(int x, int size) {
    int left, right, p;
    while (x < size) {
        left = x * 2 + 1;
        right = x * 2 + 2;
 
        if (left >= size && right >= size)
            break;
 
        p = x;
        if (left < size && arr1[p] < arr1[left])
            p = left;
        if (right < size && arr1[p] < arr1[right])
            p = right;
        if (p == x)
            break;
 
        int tmp = arr1[x];
        arr1[x] = arr1[p];
        arr1[p] = tmp;
 
        x = p;
    }
}
 
int main() {
    scanf("%d", &n);
    arr1.resize(n);
    arr2.resize(n);
 
    for (int i = 0; i < n; ++i)
        scanf("%d", &arr1[i]);
 
    for (int i = (n - 1) / 2; i >= 0; --i)
        down_heap(i, n);
 
    for (int i = n - 1; i >= 0; --i) {
        arr2[i] = arr1[0];
        arr1[0] = arr1[i];
        down_heap(0, i);
    }
 
    for (auto a : arr2)
        printf("%d\n", a);
 
    return 0;
}

3. 시간복잡도

힙 정렬 알고리즘은 간단히 쓰면 다음의 단계를 거친다.

1) 주어진 배열로 힙을 만든다.

2) 루트노드를 새로운 배열로 옮기고, 힙의 말단으로 루트를 대체한뒤, 다운힙 시킨다.

1번의 과정은 얼마나 걸릴까?

우선 힙을 만드는데 down_heap을 썼던 점을 기억하자.

down_heap은 결국엔 이진트리의 높이만큼 수행될 것이다 -> O(log n)

또한 배열의 맨 뒤 부터 밑으로 조져버린다는 점에 의해 -> O(n * log n) 안에 수행된다.

2번 과정도 동일하다. O(1)에 루트노드에 접근할 수 있으며, 다운 힙은 O(log n) 안에 수행된다. 이를 n개에 대해 연산한다.

따라서 O(n * log n) 임을 알 수 있다.