대엉코딩

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) 이지만

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

0. heap?

 - 구조 조건과 순서 조건을 가지고 있는 자료구조 이다.

 - 구조 조건 : 이진트리인데 갚이가 h 일 때 h-1까지는 full binary tree 이고 h번째에는 왼쪽부터 차례대로 채운다.

 - 순서 조건 : 부모노드는 자식노드 보다 크다 (max-heap 일 때) , 직계가 아닌 노드 끼리는 상관이 없다.

1. heap sort?

 - 위에서 언급한 heap 이라는 자료구조를 이용한 sort 방법이다.

 - heap의 특성을 생각 한다면 ? n개의 정보를 sort하기 위해선

 - data를 heap 구조로 construct 하면 root 노드 에 있는 값이 가장 큰 값이므로 그 값을 빼오면 된다. 

    (n번의 삭제연산을 수행 하면 sort가 완료된다.)

2. delete(root) and fixheap ? (downheap)

 - 루트에 있는 노드(제일 큰값을) 가져갔다고 하자. 그러면 남은 노드들로 다시 heap을 만족하도록

   트리를 구성해야 그 다음 루트노드를 또 삭제할 수 있다 (두 번째로 큰값이겠죠? 전체에서? )

 - 그렇다면 생각 해보자 ..... 루트를 제외하고 남은 트리에서 heap이 되게 하려면

 - 구조 조건과 순서 조건을 만족해야 하는데...... 어떤 것을 만족하는게 더 쉬울까 ? ----> (구조조건?)

 - 왜?? 만약에 n-1개의 노드가 남아 있다고 할때 heap의 구조조건을 만족하도록 만드는 모양은 하나뿐이다.

    ( 즉 위치로 보자면 어디 위치의 노드가 없어지느냐 ? 맨 밑 리프 노드 열에서 가장 오른쪽의 노드 !)

    ( 이 위치는 O(1) 에 바로 찾을 수 있다...! ....왜? heap은 배열로 구현 하기 때문에 맨 마지막 index의 노드!)

 - 그럼 일단 가장 오른쪽에 위치한 리프노드를 루트 노드로 덮어 쓰자 ! --->구조 조건은 만족 !

 - 이제 순서조건을 생각해보자 .... 일단 루트노드로 덮어쓴 가장 오른쪽 리프 노드가 다시 자신의 자리를 

 - 찾아갈 수 있도로 해야 하는데 이 과정이 fixheap이다 !

3. fixheap 하자

 - 이제 루트노드로 올라온 가장 오른쪽에 위치한 리프노드가 다시 자기 자리를 찾아가야 한다.

 - 자식노드들 중 값이 큰 노드와 자신을 비교해서 자신이 더 작다면 그 노드의 위치로 내려간다 (그 자식노드는 올라옴)

 - 이 과정을 자신의 위치를 찾을 때 까지 반복하여 수행 한다.(recursive하게)

 - 한번의 과정에 2번의 연산 수행 (자식들 끼리 누가 더 큰지 비교, 그 큰 자식과 자신과 비교 )

 - full binary tree 이므로 h = log n  ---->  W(n) : 2logn -->Θ(logn)

4. Algorithm

지금까지 입력으로 부터 힙이 구성된 상태에서 sort를 어떻게 할 수 있는지 에 대하여 배웠습니다.

(2)에서는 입력으로 부터 heap을 어떻게 construct하고 성능분석과

힙소트의 성능을 올릴 수 있는 방법에 대하여 알아봅시다.