Heapsort

Heap

• 구조((left) Complete binary tree)와 순서(부모 key값 >= 자식 key값)를 만족하는 binary tree

 

HeapSort

• insert() -> upHeap() : 리프에서 루트까지 swap. O(logn)
• removeMax() -> deleteMax() : 끝값을 루트에 덮어씌운 뒤 리프까지 swap.
• findMax() : 루트노드의 키값 리턴. O(1)
• heapSort(E, n): 배열 E로부터 힙 H를 만든 뒤 max값을 빼서 E에 순서대로 넣는 과정을 n번 반복한다.
• deleteMax(H): 가장 마지막 노드 값을 가장 첫번째 값에 덮어씌움-> 마지막 노드 삭제-> fixHeap
• fixHeap(H, K): downHeap. 왼쪽 자식과 오른쪽 자식 중 더 큰 것과 자리 바꾸기 반복-> 리프까지 가면 빈 자리에 가장 마지막 노드 값을 옮김

constructHeap(H)   //재귀

  if(H is not a lear)

    consructHeap(H의 왼쪽 subtree)

    constructHeap(H의 오른쪽 subtree)

    fixHeap(H, root(H))

  return;

 

• Heap을 linear time에 생성할 수 있다. O(n)

Array를 이용한 Heap 구현

• 노드의 인덱스 i가 주어졌을 때,
  왼쪽 자식 인덱스: 2i
  오른쪽 자식 인덱스: 2i+1
  부모 노드 인덱스: ⌊i/2⌋

Heapsort Analysis

• k개 노드 힙의 fixHeap 비교연산 수는 최대 2log(k).
• 따라서 모든 deletion의 총 비교연산 수는 최대 2*Σ(k=1부터 n-1까지)logk ∈ θ(nlogn)
  * n-1인 이유: 노드가 한 개 삭제되고 나서 fixHeap하기 때문.
• 정리: worst-case일 때 Heapsort의 키 비교연산 수는 2nlog(n):힙수정 + O(n):힙생성

Accelerated Heapsort

• 기존 fixHeap은 worst-case에서 2h번의 비교연산을 한다. 이를 개선하자.

1. 절반 높이까지 자리를 교체하며 내려간다.
2. 높이가 h/2인 지점에서 부모와 자신 키(K) 값을 비교해 위로 올라갈지, 아래로 내려갈지 결정한다.
3. 위로 올라가야 할 경우 upHeap으로 끝, 내려가야 할 경우 절반 높이까지 내려가는 과정을 반복한다.

Accelerated Heapsort Analysis

• 내려가거나 upHeap하는 연산은 Total h. h/2만큼 내려가고 h/2만큼 올라가거나 내려가다가 중간에 올라가거나 h/4, h/8, ... 만큼 계속 내려가거나. 각각은 모두 h만큼의 연산이 필요하다.
• worst-case는 bubbleUpHeap이 호출되지 않고 계속 내려가는 경우인데, 이때는 올라갈지 내려갈지(해당 부분의 부모 키값과 K를 비교하는) 체크하는 연산이 log(h)번 필요하다.

• 즉, worst-case일 때 w1 = h+log(h)번의 연산을 한다. heapSort할 땐 removeMax를 n번 호출하므로
   w­n = n(h+logh) = n(logn + loglog­n)