[알고리즘] Sort - 힙정렬(heap sort) - 1

Sort - 힙정렬(heap sort) - 1  

어원인지 모르겠지만 쌓아놓은 더미가 heap의 사전적 의미이다.

이번시간에는 힙 정렬에 대해서 알아보자

힙 정렬은 힙, 바이너리 힙, 이진 힙이라고 부르는 자료구조를 이용하는

정렬 알고리즘이다.

(여기서 힙은, 메모리 영역인 힙과는 다른 말이다)

힙 정렬의 특징은 다음과 같다.

1)최악의 경우에도 시간 복잡도가 nlogn이 되는 빠른 정렬이다.

2 )힙 정렬은 알고리즘을 구현하는데 추가 배열이 필요하지 않다.

3) 힙 이라는 자료구조를 이용해서 정렬을 한다.

따라서 알고리즘을 구현하기 앞서, 힙 이라는 자료구조에 대해

알아보도록 하자

힙(Heap)은 

1) complete binary tree 이면서

2) heap property를 만족해야 한다.

complete binary tree 란 무엇일까.

위의 그림을 보면 2개의 tree 그림이 있다.

이진트리(binary tree)란 자식 노드가 2개씩 분화되는 tree 이다.

따라서, 위의 2개 tree는 모두 이진 트리이다.

이진 트리는 자식 노드가 생성될 때 왼쪽 부터 생성된다.

이진트리중에 full binary tree는 말 그대로

모든 레벨의 노드 들이 꽉 차있는 형태이다.

complete binary tree는 n-1 레벨까지는 full binary tree이고

맨 마지막 레벨은 연속해서 하나씩 채워 져야한다.

(오른쪽이 비워져 있어도 상관 없다.)

따라서 full binary tree는 자체만으로 complete binary tree이다.

위의 2번째 조건에서 heap property를 만족해야 한다고 했는데

1) max-heap property - 부모는 자식보다 데이터가 크거나 같다.

2) min-heap property - 부모는 자식보다 데이터가 작거나 같다.

2개의 조건으로 나뉜다.

max와 min모두 대칭적 관계이므로 모든 알고리즘이 적용되나

상황에 따라서 간단하게 사용할수 있는 것을 쓰며,

여기서는 max-heap property를 다루도록 한다.

(a)는 3개 다 heap이다.

complete binary tree의 모양과 heap property을 만족한다.

(b)의 3개의 예는 heap이 아니다

트리의 모양자체는 이상이 없으므로 complete binary tree의 모양을 만족한다

그러나 heap property를 만족하지 않으므로 heap이 아니다

(c)의 2개도 heap이 아니다.

 complete binary tree의 모양을 만족하지 못한다.

a,b,c 3개가 다 heap이다.

자세히 살펴보면 a,b,c는 동일한 데이터를 가지고 있는데

이는, heap에 저장되어있다는 데이터가 동일하다고 해서 

유일함을 결정하지 않는다는것이다.

다시 말해, 여러가지 모양의 heap이 존재할 수 있다는 것이다.

개념적으로는 binary tree이지만

실제적으로는 heap을 1차원 배열로 표현 할 수 있다.

같은 레벨에서 왼쪽부터 배열로 저장하면 1차원 배열이 된다.

1차원 배열에 저장한다면 누가 누구의 부모고 자식인지 어떻게 알수 있을까.

물론 일반적인 트리는 알수가 없으나 complete binary tree이므로

인덱스 만으로 부모/자식의 관계를 알 수 있다.

1번의 왼쪽은 2번 오른쪽은 3번이다.

2의 왼쪽은 4번, 오른쪽은 5번이다.

즉 어떤 노드가 i 번이라면 자식에 대해서 왼쪽은 2*i 번, 오른쪽은 2*i+1번 이다.

거꾸로 생각해서 어떤 노드가 j번이라면 부모는 j/2번에서 소수점을 제외한 수이다.

따라서 실제로 1차원 배열에 저장하더라도

인덱스만 보면 누구의 부모/자식인지 판별할수 있으므로 

불필요하게 트리를 구현할 필요가 없다는 것이다.

우리가 heap이라는 자료구조를 다루기 위해 필요한 연산이 있는데

그것은 max-heapify라고 하자

연산을 수행할 전제 조건은 다음과 같다.

1) 트리 전체모양은 complete binary tree이다.

2) 왼쪽 서브트리(subtree)는 그 자체로 heap이다.

3) 오른쪽 서브트리(subtree)는 그 자체로 heap이다.

여기서 유일하게 루트만이 heap property를 만족했을 때

이를 만족시키게 변화시키는것을 max-heapify 연산이 라고 정의 한다.

루트 노드가 정렬되기 위해서는

누군가가 루트의 자리를 대체하고 루트는 그 자리로 가야한다.

연산은 간단하다.

루트 노트에서 자신의 노드중에 더 큰값을 선택한다.

그리고 그 값과 자리를 바꾼다.

이 과정을 마지막 레벨까지 반복한다.

MAX-HEAPIFY(A, i){
    if there is no child of A[i]
        return;
    k <- index of the biggest child of i;                                                                  
    if A[i]>=A[k]
        return;
    exchange A[i] and A[k];
    MAX-HEAPIFY(A, k);
}
 

위의 과정을 자세히 봤을때 동일한 과정을 반복하고있으니

heapify는 recursion으로 구현이 가능하다.

첫번째 조건은 base case이다.

자식 노드가 없다는 것은 가장 아래의 레벨까지 내려왔다는 뜻이므로

현재 노드는 리프(leaf)이다.

따라서 return 해주게 된다.

만약에 자식이 있다면 더 큰쪽을 k라고 한다.

자식이 1명만 있는 노드일 경우 1개의 노드를 k 로 지정한다.

자식 노드 보다 크다면 정렬된 것 이므로 리턴한다.

그렇지 않으면 큰 쪽의 자식 노드와 자리를 변경하며 max-heapify를 재귀 호출 한다.

MAX-HEAPIFY(A, i){
    while A[i] has a child do
        k<- index of the biggest child of i;                                                                
        if A[i]>= A[k];
            return;
        exchange A[i] and A[k];
        i=k;
    end
}