[알고리즘] 6장 힙 정렬(Heap Sort)

6장 힙 정렬(Heap Sort)

https://www.youtube.com/watch?time_continue=1731&v=4ULxG2Q3vgU&feature=emb_title

Heap Sort

• 최악의 경우 시간복잡도 O(nlog2n)
• 이진 힙 자료구조 사용

Heap의 정의

• 완전 이진 트리이면서 Heap property를 만족하는 것

  Tree : 계층적 관계를 표현한다
  • Full Binary Tree : 모든 레벨에 노드들이 꽉 차있는 형태
  • Complete Binary Tree : 마지막 레벨을 제외하면 완전히 꽉 차있음, 마지막 레벨에는 가장 오른쪽부터 연속된 몇 개의 노드가 비어있을 수 있음
• 

Heap은 일차원 배열로 표현이 가능하다 : A[1..n]

Heap은 complete binary 형태이기 때문에 index로 부모-자식 관계를 파악할 수 있다

• 루트 노드 : A[1]
• A[i]의 부모 : A[i/2]
• A[i] 의 왼쪽 자식 노드 : A[2i]
• A[i] 의 오른쪽 자식 노드 : A[2i+1]

기본 연산 : MAX-HEAPIFY

• 유일하게 루트만 heap property를 만족하지 않는 경우, 전체를 힙으로 만드는 연산이 heapify이다.

• 위 상황이라면 루트 노드의 값이 가장 작은 것을 의미하기 때문에 해당 값을 제일 밑으로 보내주면 될 것 같다.

  → 두 자식들 중 더 큰 쪽이 나보다 크면 교환한다. 더 이상 비교할 자식이 없으면 종료한다.

MAX-HEAPIFY : Recursive version

// pesudo-code
max-heapify(A, i) {
    // 1. 자식이 없다면 return
    // 2. 자식이 있는 경우
        // 2-1. i보다 큰 자식을 k라고 한다.
        // 2-2. A[i] >= A[k]이면 heapify가 완료된 것으로 return
        // 2-3. 위 조건이 아니면 두 값을 교환한다.
    // 3. max-heapify(A, k) 호출
}

MAX-HEAPIFY : Iterative version

// pesudo-code
max-heapify(A, i) {
    while (A[i]가 자식 노드가 있다면) {
        // 1. i보다 큰 자식을 k라고 한다.
        // 2. A[i] >= A[k]이면 heapify가 완료된 것으로 return
        // 3. 위 조건이 아니면 두 값을 교환한다.
        // 4. i = k
    }
}

Heap sort - O(nlog2n)

1. 주어진 데이터로 힙을 만든다.
2. 힙에서 최대값(루트)을 가장 마지막 값과 바꾼다. (배열로 치면 가장 앞에 위치)
3. 힙의 크기가 1 줄어든 것으로 간주한다.(n = n-1) 즉, 가장 마지막 값은 힙의 일부가 아닌 것으로 간주한다.
4. 루트 노드에 대해서 HEAPIFY(1) 한다.
5. 2~4번을 반복한다.

1. BUILD-MAX_HEAP(A)               : O(n)
2. for i <- heap_size downto 2 do  : n-1 times
3.   exchange A[1] <-> A[i]        : O(1)
4.   heap_size <- heap_size - 1    : O(1)
5.   MAX-HEAPIFY(A, 1)             : O(log2n)