[알고리즘] 힙정렬(Heap sort)

 

 

알고리즘

 

 

힙정렬(Heap sort)

 

 

 

 

 

---

힙 정렬은 트리 구조를 이용하기 때문에 이해하는데 가장 오랜시간이 걸렸어요.

저는 자료구조를 배우지 않은 상태에서 알고리즘을 시작했거든요.

그래서 이번엔 저 처럼 자료구조를 배우지 않고 알고리즘을 먼저 시작한 사람들을 대상으로

설명할 예정입니다.

---

 

 

 

이해 순서

 

1.  트리의 구조를 이해한다.

2. 이진 트리를 이해한다.

3. 완전 이진 트리를 이해한다.

4. 최대힙과 최소힙을 이해한다.

5. 힙정렬을 이해한다.

주의 : 1 ~ 4 과정은 자료구조 게시판에 자세히 올릴 예정이므로 간단하게 설명하겠습니다.

 

 

 

트리 구조란 ?

 

: 나무의 뿌리(root) , 줄기(trunk), 잎(leaf) 처럼 특정한 관계를 갖고 있는 자료들을 의미합니다. 그림을 보면 마치 뒤집어 놓은 나무처럼 보이죠 ? 가장 위에 있는 자료 A 는 뿌리(root) 를 의미합니다. 그리고 뿌리에서 줄기들을 타고 뻗어나가는 B, C, D, F, I 등을 노드라고 부릅니다. 이 노드는 다시 부모노드와 자식노드로 개념이 나뉩니다. 예를들어, A 와 B를 보겠습니다. A 는 B의 부모노드 , B는 A의 자식노드가 되겠지요.

 가장 밑에 정렬된 자료들을 보니 자식노드가 하나도 없는 자료들이 있네요. 이런 노드들을 잎(leaf) 이라고 부릅니다. 자 이정도면 어느 정도 트리에 관한 용어들을 숙지했습니다. 그림을 보면 이런 구조를 어떻게 만드나 걱정하시겠지만, 정말 이런 구조를 시각적으로 구현하는 것이 아니고 배열의 자료들끼리 특정한 관계를 설정해줌으로써 이러한 계층구조를 만드는 것입니다.

 

 

 

 

이진트리 ?

 

: 이진트리는 모든 노드들의 자식노드가 2개 이하인 트리를 의미합니다. 간단하죠 ? 자 이진트리는 크게 "완전이진트리" 와 "포화이진트리"로 나뉩니다.

 

완전이진트리는 트리의 깊이를 k라고 할때, 깊이가 k-1 인 모든 노드들의 자식노드는 2개이고 깊이가 k 인 즉 최하단에 위치한 잎(leaf)들이 모두 왼쪽부터 채워진 구조를 의미합니다.

 

 

 

 

 

포화이진트리는 깊이가 k인 이진트리가 있다고 합시다. 그럼 깊이 k 에 존재하는 자식노드가 모두 2개인 트리구조를 의미합니다. 그림을 그려보면 모두 삼각형이 완성이 되겠죠 ? 어차피 힙정렬은 완전 이진트리를 이용하기 때문에 간단하게 이해만하고 넘어가겠습니다~

 

 

 

 

최대힙과 최소힙 

 

최대힙이란 모든 자료에서 부모노드의 값이 자식노드보다 큰 구조를 의미합니다. 단, 완전이진트리 구조가 전제가 되야합니다. 힙(Heap)자체가 완전이진트리에서 고안된 방법이기 때문입니다. 예를들어 A=3 인데 자식노드인 B=2 , C=1 이라면 A 가 자식노드보다 크기 때문에 최대힙이라고 할 수 있습니다.

 

자연스럽게 최소힙이란 부모노드의 값이 항상 자식노드보다 작은경우를 의미합니다. 이 구조를 이용하면 빠르게 최댓값과 최솟값을 찾을 수 있습니다. 예를들어, 어떠한 완전이진트리를 최대힙 구조로 만들면 항상 뿌리(root)는 자료의 최댓값이 됩니다. 이렇게 최댓값을 찾아서 순차적으로 정렬시키는 방법이 바로 힙정렬입니다. 이제 조금 이해가 되시나요 ?

 

 

 

 

 

힙 정렬 (Heap sort)

 

임의의 배열을 오름차순으로 정렬 한다고 가정하겠습니다. 배열에는 이미 인덱스 값들이 정해져있기 때문에 트리구조를 갖추고 있다고 할 수 있습니다. 이 말이 잘 이해하기 힘들텐데 다음 사진을 보면 크기가 15인 배열이 있을 때 해당 데이터와 인덱스를 나타냈습니다. 트리 구조에서 인덱스 값은 붉은색, 데이터는 검은색으로 나타내고 있습니다.

 

 

 

 

이제 왜 배열이 곧 트리구조인지 이해가 가시나요 ? 굳이 시각화 하지 않아도 인덱스와 데이터값만 가지고 있다면, 특정 조건을 성립시켜서 원하는 트리구조를 만들 수가 있습니다. 그런데 이상한 부분이 하나 있지요 ? 배열의 첫번째 인덱스는 0인데 트리구조의 인덱스는 1 부터 카운트 하고 있습니다.

이건 바로 부모노드와 자식노드의 관계 때문입니다. 1,2,3의 부분트리구조를 보겠습니다. 부모노드(1)을 기준으로 (부모노드) X 2 = (왼쪽 자식노드) , (부모노드) X 2 +1 = (오른쪽 자식노드) 라는 관계가 성립됩니다. 만약 0부터 카운트 한다면 왼쪽 자식노드는 계산상 오류가 생기겠죠? 하지만 개발자 마다 0부터 카운트 하는 경우도 있습니다. 이때는 계산이 조금 달라집니다.

(부모노드)X2 + 1 = (왼쪽 자식노드), (부모노드)X2 + 2 =(오른쪽 자식노드) 이렇게 관계가 이해됬다면 배열에서 최대힙과 최소힙을 만들 수 있겠죠 ?

지금 까지 저의 설명은 힙정렬을 이해하기 위한 자료구조의 설명이였습니다. 상세한 힙정렬의 설명은 여기로 들어가시면 배우실 수 있습니다. 

 

 

 

시간복잡도

 

 

 

 

 

 

 

코드

 

 
#include <iostream>
 
using namespace std;
 
void printArr(int arr[], int len) { //배열 출력 함수
    int i;
    for (i = 0; i < len; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}
 
void swap(int* val1, int* val2) { // 스왑 함수
    int tmp = *val1;
    *val1 = *val2;
    *val2 = tmp;
}
 
void heapify(int arr[], int len, int parent) { //인덱스를 0부터 카운트하는 경우
    int largest = parent; //부모 노드
    int l = 2 * parent + 1; //왼쪽 자식
    int r = 2 * parent + 2; //오른쪽 자식
    //heapify는 힙구조를 만드는 과정을 의미
    
    if (l < len && arr[l] > arr[largest]) {
        largest = l;
    }
    if (r < len && arr[r] > arr[largest]) {
        largest = r;
    }
    /*왼쪽 자식과 오른쪽 자식과 비교해서 
    더 큰 값의 인덱스를 largest에 넣는 과정*/
    
    if (largest != parent) {        
 
        swap(&arr[parent], &arr[largest]);
    
        heapify(arr, len, largest);
    }
}/* 큰 값이 바뀐경우 스왑을 하고 순환호출을 해서
 바뀐 인덱스에 대해서 한버더 heapify*/
 
 
void heapSort(int arr[], int len) {
    
    for (int i = len / 2 - 1; i >= 0; i--) {
        heapify(arr, len, i);
    }
    //최대힙을 만드는 과정
    for (int i = len - 1; i >= 0; i--) {
         
        swap(arr[0], arr[i]);
        //arr[0]은 최댓값, arr[i]는 마지막 인덱스
        heapify(arr, i, 0);
    }//교체후 다시 힙정렬을 만든다.
}
 
int main() {
    int arr[] = { 1, 21, 36, 28, 7, 90, 41, 85, 71, 4 };
    int len = sizeof(arr) / sizeof(arr[0]);
    //arr의 길이
    cout << "정렬 전 : ";
    printArr(arr, len);   
 
    heapSort(arr, len); 
 
    cout << "정렬 후  : ";
    printArr(arr, len);   
 
    return 0;
}
 
 
 

 

 

 

 

출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html