Chap 6-5. 힙 정렬(Heap Sort)

먼저, 힙이라는 자료구조에 대해서 알아보고 이를 이용한 정렬 방법에 대해 알아보자!

힙(Heap)을 공부할 때 항상 가수 마마무의 노래 중 힙(HIP)이 생각난다 ㅎㅎ 배경음악으로 틀고 공부해보자...ㅎ

 

😎힙(heap)이란?

힙 ("이진 힙"이라고도 한다)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위하여 고안된 완전 이진 트리(Complete Binary Tree)를 기본으로 한 자료구조이다. 

힙이라고 하는 것은 우선순위큐를 구현하기 위해 만들어진 데이터 타입이라고 할 수 있다.

여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.(빠르다니.. 완전 HIP한 Heap 이다.)

 

✔️힙 조건 : 각 노드의 우선 순위가 자식 노드의 우선순위보다 높거나 낮을 때 

✔️힙 종류 : 최대 힙(Maximum Heap): 가장 큰 값이 루트에 저장 (높은 경우), key(부모노드) ≥ key(자식노드)

                  최소 힙(minimum Heap): 가장 작은 값이 루트에 저장 (낮을 경우), key(부모노드) ≤ key(자식노드)

✔️힙 높이 : 완전 이진 트리이므로, n개의 노드를 가지고 있다면 힙의 높이가 logn 이다.

✔️마지막 레벨을 제외하고는 각 레벨에 노드들이 꽉 차 있는 형태이어야 한다.

 

*원래의 이진탐색트리는 키값의 중복을 허용하지 않지만(항상 left < root < right를 만족해야 한다) 이진 트리인 힙에서는 key의 중복을 허용한다.

 

 

🤟heap의 구현 방법

heap은 “배열"을 이용하여 구현한다.

완전 이진 트리이므로 마지막 레벨을 제외하고 각 레벨의 노드들이 꽉 차 있다.

-> 이는 배열로 표현한다면 배열 중간에 빈 공간 없이 순서대로 인덱스마다 값이 연속적으로 들어간다는 것을 의미한다. 

-> 각 노드에 번호가 배열의 해당 인덱스가 되며 인덱스로 바로 접근 가능하다.

 

(*배열이 아닌 연결 리스트로 구현은 가능하지만 부모 노드 포인터가 더 필요하고 구현이 복잡하다고 하다.)

 

✔️배열을 이용했을 때의 장점

=> 부모 노드와 자식 노드를 찾기 쉽다.

힙을 삭제 혹은 추가를 한 이후 힙의 형태를 유지하기 위해서는 부모, 자식의 값을 찾아가서 자리를 재배치하는 것이 필요하다.

다음의 식을 통해 부모 혹은 자식의 노드에 한 번에 접근할 수 있다. 

 

left child index = parent_index * 2

right child index = parent_index*2 + 1

parent index = child_index / 2 (단, i가 홀수이면 정수 부분만)

 

 

힙 삽입(insertion)

일단 하나의 원소가 삽입되면 맨 아래에 삽입된다.

-> 위로 올라가면서⬆️  부모 노드들과 값을 비교한다.

-> 부모 노드보다 크다면 교환한다.

*신입사원이 들어오고 능력에 따라 위로 승진하는 것과 비슷하다. 

힙 삭제(deletion)

일단 루트 노드를 삭제

-> 마지막 노드를 루트 노드로 이동

-> 루트에서 단말 노드까지의 경로에 있는 노드들을 아래로 내려가면서 비교한다. 

-> 힙 조건에 맞지 않는다면 서로 교환하여 heap 성질을 만족시킨다.

*회사에서 사장의 자리가 비게 되면 일단 급한대로 말단 사원을 임시로 사장 자리에 두고 위에서 부터 전체 노드를 비교하며 능력이 좋은 사람이 위로 가게 하는 것이다.

---

😎힙 정렬 (heap Sort)

최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법이다.

 

정렬할 입력으로 최대 힙(Max heap)을 만든다.(입력하고 나서 힙을 유지하기 위해 정렬을 한다)

이때, 최대값이 계속 삭제가 되면서 sort되는 원리이다. → 즉, 삭제한 원소들을 차례대로 모아놓으면 정렬된 배열이 된다.

*힙에서의 삭제는 특정 인덱스를 선택하여 삭제하는 것이 아니라 무조건적으로 루트 노드가 삭제되는 것을 의미한다.

 

🤟 과정

한 번에 하나씩 요소를 heap에서 delete 하여 저장한다. 

 

(0) 먼저, 정렬해야 할 n개의 요소들을 max heap으로 구성

최대 힙이기 때문에 항상 힙 루트에 가장 큰 수가 있다. 

 

(1) 루트와 힙의 가장 마지막 노드를 교환한다. ⇒ 가장 큰 수를 배열의 맨 뒤로 옮긴 것

 

(2) 힙에서 root의 값(최대값)를 꺼내서 배열의 뒤로 저장한다.

 

(3) 힙 크기를 1개 줄인다.(노드 하나가 삭제되는 효과이다)

 

(4) 루트에 새로 저장된 숫자로 인해 위배된 힙 조건을 해결하여 힙 조건을 만족시킨다.

*방법 DownHeap() = 루트로부터 자식들 중에서 큰 값을 가진 자식과 비교하여 힙 속성이 만족될 때까지 숫자를 교환하며 진행

 

(5) 이 과정을 반복하여 정렬한다.

 

(6) 그러면 뒤에서부터 차례대로 하나씩 정렬되어 배열에 저장될 것이다.

 

 

 

🤟 의사코드

입력: 입력이 A[1]부터 A[n]까지 저장된 배열 A 
출력: 정렬된 배열 A

1. A의 숫자에 대해서 최대 힙을 만든다.
2. heapSize = n   // 힙의 크기를 조절하는 변수
3. for i = 1 to n-1
4.    A[1] ↔ A[heapSize]         // 루트와 힙의 마지막 노드 교환
5.    heapSize = heapSize -1   // 힙의 크기 1 감소= downheap( 자식노드들과 비교하여 내려감)
6.    DownHeap() // 위배된 힙 조건을 만족시킨다.
7. return A

 

🤟 코드 구현

#include <stdio.h>
#include <stdlib.h>

#define N 100

typedef struct
{
    int heap[N];
    int heapSize; //삽입 연산을 할 때 마지막 노드에 대입해야 하므로 
}HeapType;

void init(HeapType *H)
{
    H-> heapSize = 0; //H라는 주소로 가봐, 그 안에 heapSize가 있을거야 그걸 0으로 만들어 

}

void upHeap(HeapType* H) //노드를 추가하고 싶을 때 맨 아래에 추가하고 다시 정렬 
{
    int i = H-> heapSize;
    int key = H-> heap[i]; //삽입된 노드를 다른 공간에 저장해놓기 
    while((i != 1) && (key > H-> heap[i/2] )) //2가지 조건을 만족해야 한다 (i = 1이 아니고(루트가 아니고, 루트면 더 이상 볼 게 없음 ), key가 부모 노드보다 크다면)
    {
        H-> heap[i] = H-> heap[i/2]; //부모 노드와 자리를 바꾼다. 
        i /= 2; //부모 노드로 올라감 
    }
    H->heap[i] = key; //최종 위치 결정 
}

void insertItem(HeapType *H, int key)
{
    H->heapSize++; //삽입할 것이기 때문에 힙 사이즈를 증가 
    H-> heap[H->heapSize] = key; //마지막 노드에 삽입 
    upHeap(H);
}

void downHeap(HeapType *H) // 루트 노드 삭제하고 싶을 때 하나를 빼고 다시 정렬 
{
    int item = H->heap[1];
    int parent = 1; //루트 노드
    int child = 2; //왼쪽 자식 노드 = 이진 트리는 항상 왼쪽 자식이 먼저이기 때문에 

    while(child <= H->heapSize){
        if((child < H-> heapSize)&&(H-> heap[child + 1] > H->heap[child])) //child 오른쪽으로 최소한 1개의 노드가 있다. (형제 노드의 여부, child노드의 오른쪽자식이 있는지 보는 것이다. )
        //그리고 child의 형제노드가 더 크다면 
        {
            child++; //child를 3으로 하자 , 비교 대상을 오른쪽 child로 변경
        }
        if(item >= H->heap[child])
        {
            break; //힙 조건을 만족하므로 아무 위치 교환 없어도 된다. 
        }
        H-> heap[parent] = H->heap[child]; //자식이 더 크므로 힙조건을 만족하지 않으므로 위치 교환
        parent = child; //child가 부모 노드
        child *= 2; // 다시 child 왼쪽 자식 그리고 반복 
    }

    //비교 후 위치 고정 
    H-> heap[parent] = item;

}

void heapSort(HeapType* H)
{
    int n = H->heapSize;

    for(int i = 1; i <= n; i++)
    {
        int item = H->heap[1]; //루트에 있는 노드를 저장한다. 
        H->heap[1] = H->heap[H->heapSize]; //마지막 노드에 있는 것과 루트 노드 자리 바꿈 
        H->heap[H->heapSize] = item; //마지막 노드에 루트 노드를 넣음 
        H->heapSize--; //힙사이즈 감소 즉, 루트 노드를 맨 뒤로 보내고 이를 삭제한다는 개념
        downHeap(H);

        printf("Step %d : ", i); //과정별로 출력된다. 
        for (int i = 1; i < n; i++)
        {
            printf("(%d)", H-> heap[i]);
        }
        printf("\\n");
    }

    
}

int main()
{
    HeapType H; //힙 만들기 
    init(&H); //main함수에서 선언한 H의 주소를 넘긴다. -> 모든 함수에서 main에서 만든 것을 공유하기 위해 

    insertItem(&H ,90);
    insertItem(&H, 60);
    insertItem(&H, 80);
    insertItem(&H ,50);
    insertItem(&H, 30);
    insertItem(&H, 70);
    insertItem(&H ,10);
    insertItem(&H, 20);
    insertItem(&H, 40);

    heapSort(&H);

    return 0;
}

 

🤟  시간복잡도

(1) 힙을 만드는 시간 = O(n)

(2) for 루프틑 n-1번 수행

       루프 내부는 O(1) 시간

(3) downHeap은 O(logn)시간 (힙의 높이는 logn을 넘지 않을 것이기 때문)

⇒ O(n) + (n-1) * O(logn) = O(nlogn)

 

🤟 특징

• 큰 입력에 대해 DownHeap()을 수행할 때 자식을 찾아야 하므로 너무 많은 캐시 미스로 인해 페이지 부재(page fault)를 야기할 수 있다. 
• 최선, 최악, 평균 시간 복잡도가 동일하다. =  O(nlogn)