[Algorithm] 힙 정렬(Heap Sort)

힙 정렬(Heap Sort)

병합 정렬(Heap Sort)이나 퀵 정렬(Quick Sort)만큼 빠른 정렬 알고리즘으로 힙 트리 구조(Heap Tree Structure)를 사용하는 정렬 방법

추가적인 배열이 필요하지 않다는 점에서 메모리 측면에서 병합 정렬(Merge Sort)에 비해 효율적이며 항상 O(N*logN)을 보장한다.

이론적으로는 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort)보다 더 우위에 있다고 할 수는 있으나, 단순히 속도만 가지고 비교해보면 퀵 정렬(Quick Sort)이 평균적으로 더 빠르기 때문에 힙 정렬(Heap Sort)이 일반적으로 많이 사용되지는 않는다.

 

트리(Tree)

가지를 뻗어나가는 것 처럼 Data가 서로 연결되어 있는 자료구조

 

이진 트리(Binary Tree)

컴퓨터 안에서 Data를 표현할 때 데이터를 각 Node에 담은 뒤 Node를 두 개씩 이어붙이는 구조

Root: Tree의 최상단 Node

Leaf: Tree의 최하단 Node

 

완전 이진 트리(Complete Binary Tree)

Data가 Root Node부터 시작해서 자식 Node가 왼쪽 자식 Node, 오른쪽 자식 Node로 차근차근 뻗어나가는 구조의 이진 트리(Binary Tree)

힙(Heap)

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

최대 힙(Max Heap): 부모 노드가 자식 노드보다 큰 힙

-> 힙 정렬을 하기 위해서는 정렬할 데이터를 힙 구조로 변형해야 한다.

위쪽으로 보았을 때는 최대힙이 형성되어있으나 아래쪽으로보았을 때는 데이터 5를 가지는 노드 때문에 최대힙이 형성되어있지 않은 경우

☞ 해당 노드의 자식 노드 중 자신보다 큰 값과 위치를 변경(힙 생성 알고리즘 이용)

 

힙 생성 알고리즘(Heapify Algorithm)

특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 변경하는 알고리즘으로 한 번 위치를 바꾼 후 여전히 자식이 존재하는 경우 다시 자식 노드 중에서 더 큰 자식과 자신의 위치를 바꾸는 동작을 수행한다.

특정한 하나의 노드에 대해 수행하는 것으로 해당 하나의 노드를 제외하고는 최대 힙이 구성되어있는 상태가 가정되어 있어야 한다.

힙 생성 알고리즘의 시간 복잡도

데이터의 개수가 N개일 때 노드의 높이는 logN

한 번 자식 노드로 내려갈 때마다 노드의 개수가 2배씩 증가하기 때문에 O(logN)

하지만 실질적으로 비교에 필요한 노드의 개수는 N/2개이므로 결과적으로 시간 복잡도는 O(N)

 

힙 정렬 Sequence

순서대로 배열에 저장

 

힙 구조로 변경(상향식)

 

부모노드와 가장 마지막 집합의 노드를 변경

 

가장 마지막 노드를 제외한 노드만 이용해 힙 구조로 변경 + 부모노드와 집합의 가장 마지막 노드 위치 변경 동작 반복

 

결과

 

Code

#include <iostream>
using namespace std;
#define 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 c = i;
        do{
            // root: 자기 자신의 부모
            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);
    }

    // 크기를 줄여가며 반복적으로 힙 구성
    for(int i=number - 1;i>=0;i--){
        // root node와 가장 마지막 node의 위치 변경
        int temp = heap[0]; // 0번째 index = root node
        heap[0] = heap[i];
        heap[i] = temp;

        // 다시 최대 힙 구조 만들기
        int root = 0;
        int c = 1;
        do{
            // c: root의 자식
            c = 2 * root + 1;
            // 자식 중에 더 큰 값 찾기
            // 왼쪽과 오른쪽 중 더 큰 값을 c에 담음
            if(heap[c] < heap[c+1] && c < i - 1){
                // 왼쪽 값보다 오른쪽 값이 더 크면 오른쪽 node의 index가 c에 저장됨
                c++;
            }

            // root보다 자식이 더 크면 root와 자식을 교환
            if(heap[root] < heap[c] && c < i){
                int temp = heap[root];
                heap[root] = heap[c];
                heap[c] = temp;
            }
            // c를 root로 이동시켜 반복
            root = c;
        } while(c < i);
    }

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

출력

1 3 5 5 6 6 7 8 9

 

시간 복잡도

항상 O(N*logN)의 시간 복잡도를 보장한다.