CH04 : Sorting 4 - Accelerated Heap Sort

 기존 heap sort는 $W(n) = 2n \log n + O(n)$ time이 걸린다. Acclerated heap sort의 경우 이를 $n \log n$으로 단축시킬 수 있다. (2배 speedup) fixHeap을 fixHeapFast로 개선한다. 

Acclerated Heap Sort

아이디어

 binary search에선 중앙값과 K의 비교를 통해 앞으로 살펴볼 영역의 절반을 없앤다. 즉 수평적으로 divide and conquer 전략을 사용한다. acclerated heap sort에선 수직적으로 divide and conquer 전략을 사용한다.

전략

1.  현재 heap의 height h에 대하여, $\frac {h}{2}$가 될 때까지 vacant의 위치를 내린다.
2. 현재 vacant의 key값과 부모의 key값을 비교하여,
   1. vacant>parent면 vacant 값을 위로 올린다. → bubble up (parent와 swap하며 올라감.)
   2. vacant<parent면 recursive하게 동작한다. → 현재 subheap에서 절반의 height로 내려가 parent의 key값과 비교... (1번부터 재귀)

 한 번 아래로 내려가면 그 위의 원소는 더 이상 살펴보지 않는다. (반대로, 한 번 위로 올라가면 그 아래의 원소는 더 이상 살펴보지 않는다.)

Algorithm

 핵심은 기존 heap sort의 fixHeap을 fixHeapFast로 개선하는 것이다. 이외 알고리즘은 heap sort 내용을 참고 (https://malangdubu-tech.tistory.com/24)

void fixHeapFast(Element[] E, int n, Element K, int vacant, int h)

if (h<=1) //base case
    Process heap of height 0 or 1

else //recursive case
    int hStop = h/2
    int vacStop = promote(E, hStop, vacant, h)
    //vacStop은 hStop에서의 새로운 vacant 위치
    int vacParent = vacStop/2
    if (E[vacParent].key <= K.key)
        E[vacStop] = E[vacParent]
        bubbleUpHeap(E, vacant, K, vacParent)
    else
        fixHeapFast(E, n, K, vacStop, hStop)

• 동작 설명
  • base case 
    • h=0 : 루트 노드 하나만 존재 (자식x) / h=1 : 루트 + 자식 한 레벨 (최대 2개 자식 노드)
    • 즉 힙의 크기가 매우 작아서 비교 없이 K를 바로 적절한 위치에 넣으면 되는 경우
  • recursive case
    • 멈출 height(hStop), hStop에서 K가 들어갈 자리 후보(vacStop), vacStop의 부모(vacParent) 결정
      • promote()는 현재 vacant 위치에서 자식 중 더 큰 쪽을 위로 끌어올리며 아래로 내려감. (하단 추가 설명)
    • vacParent의 key값보다 내 key값이 크면 → 위로 올라가야 하는 경우
      • 부모를 vacStop에 복사하고, bubble up
        • bubbleUpHeap()은 부모와 나를 비교해서 내가 더 크면 부모와 나를 swap. (하단 추가 설명)
    • vacParent의 key값보다 내 key값이 작으면 → 아래로 내려가야 하는 경우
      • 하위 절반 힙(hStop 깊이 이하)을 대상으로 재귀 

fixHeapFast 시각화 예시

int promote(Element[] E, int hStop, int vacant, int h)
    int vacStop
    
    if (h<=hStop)
        vacStop = vacant
    else if (E[2*vacant].key <= E[2*vacant+1].key) //오른쪽 자식이 더 큼
        E[vacant] = E[2*vacant+1] //swap
        vacStop = promote(E, hStop, 2*vacant+1, h-1) //h를 1씩 빼주며 hStop까지 내려감
    else //왼쪽 자식이 더 큼
        E[vacant] = E[2*vacant] //swap
        vacStop = promote(E, hStop, 2*vacant, h-1)
    
    return vacStop

 

void bubbleUpHeap (Element[] E, int root, Element K, int vacant)
    if (vacant==root) //base case : 최악의 경우 해당 subtree의 root까지 올라갈 수 있음
        E[vacant] = K
    else
        int parent = vacant/2 //parent의 index
        if (K.key <= E[parent].key) //여기가 맞는 자리!
            E[vacant] = K
        else 
            E[vacant] = E[parent] //swap
            bubbleUpHeap(E, root, K, parent)

Acclerated Heap Sort Analysis

fixHeapFast Analysis

최악의 경우 정의

 Acclerated Heap Sort에서 최악의 경우는 '끝까지 promote만 하는 경우'이다. 즉 K가 너무 작아서 위로 올라가지 않고 힙 아래까지 내려가게 되는 상황이다. 이 경우 promote가 vacant를 leaf까지 계속 끌고 내려가게 된다. vacant는  h/2 → h/4 → … → 1 수준까지 재귀적으로 내려간다. 

 정리하자면, worst case에서 걸리는 시간은 1. 내려갈 때마다 bubble up을 할지, 더 내려갈지 결정을 위한 비교 시간 + 2. 내려가면서 자식을 비교해서 더 큰 쪽을 위로 올리는 비교 시간 

최악의 경우 분석

 h/2 → h/4 → … → 1씩 내려감에 따라 bubble up을 할지, 더 내려갈지 결정을 위한 비교 연산은 $\log h$번 일어난다. 

 본질적으로, vacant가 level을 바꿀 때마다 한 번의 연산이 필요(bubbleUpHeap or promote)하고, 총 h(height)번의 연산이 필요하다. → 두 함수 bubbleUpHeap, promote에 의해 사용되는 비교연산의 수는 h.

• 좀 더 설명하자면, divide and conquer에 따라 h/2 → h/4 → … → 1씩 내려가지만, 그 과정에서 자식을 비교해서 더 큰 쪽을 위로 올리는 비교가 들어가기 때문에 $\log h$가 아닌 h번 비교가 필요하다. 

 결론적으로 fixHeap 한 번 수행 시 $W(n) = h + \log h$이다. 

Acclerated Heap Sort Analysis

 최악의 경우에서 fixHeapFast를 n번 호출하게 되므로, $W(n) = n(h + \log h)$

• heap은 complete binary tree이므로 $h \in O(\log n)$이다. 따라서 $W(n) = n (\log n + \log (\log n))$$= n \log n + \Theta( n \log \log n)$

 heap sort든, acclerated heap sort든 둘 다 optimal algorithm이다. 다만, optimal algorithm이라도 이처럼 더 개선할 수 있다.