4. Heap sort (힙 정렬)--(2)

1. constuct Heap

 - heap sort를 위해서는 일단 입력으로 들어온 배열을 heap의 조건을 만족 하도록 만들어 줘야한다. (구조,순서)

 - 중요한 것이 있는데 heap의 구조조건은 full binary tree 이기 때문에 사실 입력(배열) 자체가 구조조건을

   만족한다.

 - 그럼 우리는 순서 조건만 맞춰서 힙을 구성하면 된다 ! 어떻게 할 것인가? 

 -밑에 자식쪽의 서브트리는 heap조건을 만족 할 때 위와 같이 하나의 노드를 삽입하면

 -순서조건이 check 되지 않은 노드는 단 하나뿐이다. --> 이 노드에 대해서 fixheap을 수행 하면

 n+1짜리의 heap이 완성 된다. (이 과정은 O(logn) -->하나의 원소를 heap에 삽입하는))

 - 이 아이디어로 밑에서부터 heap을 구성해 나가는 것이다.

 

 

2. Analysis

 - 이제 힙을 구성하고 sort 하는 것 까지 알아보았다 .... 성능 분석을 해보자 !

 - 먼저 heap construction 부분에서 짚어보자.

- 언제가 최악의 경우? (Worst case) ---> construct힙을 하는데 계속 그 노드의 위치가 leaf노드 일 때 이다

  (끝까지 내려갈 때) 

- 각 노드가 삽입 될 때 (heap을 구성하기 위해) 자신의 자리를 찾아 갈 때 규칙을 한번은 오른쪽으로 내려가고

   그 이후에는 쭉 왼쪽으로 내려간다고 하자.

 - 저렇게 내려갈 경우 힙을 다 구성 했을 때 leaf노드로 내려간 간선이 겹쳐지는 일이 없다 !

    (서로 다른색이 지나갈 때 지나간 간선을 다른 노드가 지나갈 때 그 간선을 지나가는 일이 없다)

 - construct heap 과정에서 하는 총 비교연산의 수 <= 2(비교연산) * n-1(간선의 수) ---> O(n)

 - heap sort의 최악의 경우 --->  O(2nlogn)  (sort)   +   O(n) (힙 구성)  -->  O(nlogn) 이다

 - 대소비교 연산을 이용한 sorting의 경우 O(nlogn)보다 빠를 수는 없으므로 optimal 이라고 할 수 있다.

 

 

3. Accelerate Heapsort (BubbleUpHeap)

-- > heap sorting  과정에서 fixheap을 할 때 각 단계에서 노드는 두번의 비교연산을 수행했었다.

      ( 둘 중의 누가 더 큰 자식인가 )  +  (본인과 더 큰 자식과의 비교)

- 이렇게 매번 내려갈 때 마다 두번의 비교연산을 하지 말고 한번 (둘 중의 누가 더 큰 자식인가)

   만 비교하고 무조건 그 큰 자식 쪽으로 내려간다 ( 언제까지? h/2 즉 절반정도 내려올 때 까지 )

- h/2 정도 까지 내려왔을 때 부모 노드와 비교연산을 한번 실시한다..!

- 1) 부모노드가 더 크다면? (조건만족) -->다시 나머지 h/2에 대해서 recursive 하게 다시 수행

      --> 다음엔 h/4만큼 가고 다시 비교하고...또 reculsive....!

  2) 부모노드가 작다?? --> 너무 많이 내려왔다....비교를 통해 다시 위로 올라가 내 자리를 찾아간다.

 

 

3-1 Accelerate Heapsort Analysis

 - 연산의 수를 살펴보자 (최악의 경우)

 - h/2 (이만큼 한번의 연산을 통해 내려온다) + 1(부모노드와 비교) + h/4 (다시 진행) +1 ......

   <= h (h/2+h/4+.......) + logh (1+1+...... --->log 높이)  라고 할 수 있겠다 

 - h= logn 이다 즉 . 이 방법을 통해 서 우리는

 - worst case가 nlogn+Θ(nloglogn) 임을 알 수 있다.

 -점근 분석을 하면 최악의 경우는 앞에서 본 힙소트(O(2nlogn)) 과 O(nlogn+nloglogn) 모두 O(nlogn) 이지만

 - 비교 연산의 수는 절반 정도 줄여서 성능을 향상 시킬수 있다고 생각할 수 있다.