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

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하고 성능분석과

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