[Algorithm] 힙 정렬(Heap Sort)

힙 정렬이란?

힙 트리 구조를 이용하는 정렬방법이다.

힙이란 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리이다. 힙에는 최대힙과 최소힙이 존재한다.

최대힙이란 부모 노드가 자식 노드보다 큰 힙이다.

만약 중간의 노드 때문에 최대 힙의 조건이 만족 되지 않는다면(아래의 예시 중 5 때문에 최대힙 조건이 만족되지 않는다.)

ex
			10
            /\
           5  8
          /\
         7  3

그 노드의 자식 들 중에서, 더 큰 값이랑 해당 노드랑 위치를 바꿔준다.

ex
			10
            /\
           7  8
          /\
         5  3

이런 힙 생성 알고리즘의 시간 복잡도는 트리의 높이와 같다. 즉 logN 이다.(한 단계 씩 내려갈 때 마다 노드의 수가 2배씩 커지기 때문)

힙 정렬은 이렇게 생성 된 힙 트리 구조를 이용하는 것이다.

힙 트리 구조를 완성하면, 가장 부모 노드의 수는 가장 큰 수 일 것이다.

이때 가장 마지막 노드와 가장 부모 노드의 수를 바꿔 준 후, 다시 힙 트리 구조를 생성해준다.

그리고 나서, 다시 부모 노드와 아까 바꿔준 마지막 노드를 제외한 마지막 노드를 바꿔주고, 이 과정을 반복하면 정렬된다.

#include <stdio.h>
#include <iostream>

using namespace std;

int number = 9; // 전체 데이터의 수 
int heap[9] = {7, 6, 5, 8, 3, 5, 9, 1, 6}; // 정렬할 데이터 
int main(void){
    // 최대 힙 트리 구조로 만들어 준다. 
    for(int i=1;i<number;i++){
        int child = i;
        do{
            int root = (child-1)/2; // 특정한 노드의 부모 노드

            // 부모의 값 보다 자식의 값이 더 크면 위치 변경
            if(heap[root]<heap[child]){
                int temp = heap[root];
                heap[root] = heap[child];
                heap[child] = temp;
            } 
            child = root; // 자식이 부모로 이동(상향식)
        } while (child != 0);
    }

    // 크기를 줄여가며 힙 구성
    for(int i=number-1;i>=0;i--){
        // root와 가장 마지막 원소 교환 
        int temp = heap[0];
        heap[0] = heap[i];
        heap[i] = temp;

        int root = 0;
        int child = 1;

        // 힙 구조 만드는 부분 
        do{
            child = 2 * root + 1; // 첫 번째 자식 

            // 두 자식 중에 더 큰 값을 찾기
            // 오른쪽 자식 값이 더 크다면, child값 ++
            if(child < i-1 && heap[child] < heap[child+1]){
                child++; 
            }
            // root보다 자식이 더 크면 교환
            if(child < i && heap[root] < heap[child]){
                temp = heap[root];
                heap[root] = heap[child];
                heap[child] = temp;
            }
            root = child; // child를 root로 이동시킴(다음 노드 검사)
        }while(child < i);
    }

    for(int i=0;i<number;i++)
        cout << heap[i] << ' ';
    
    return 0;
}

시간복잡도

힙 정렬의 시간복잡도는 힙 생성 알고리즘(logN) 전체 원소의 수(N)이다. 즉, O(N logN)이다.

퀵 정렬과 병합 정렬에 비해 효율적이다. 그러나 속도만 가지고 본다면 퀵정렬이 더 빠르다.

reference: https://www.youtube.com/watch?v=iyl9bfp_8ag&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=11