Algorithm 5 - Heap sort

 Heap sort
- Heap : complete binary tree(CBT) & Heap property
- CBT : 마지막 level을 제외하고 모든 level이 채워진 이진 트리이며, 마지막 level은 항상 왼쪽부터 채워져야 한다는 규칙을 가지는 tree.
- Heap property : Max heap ( parent node가 항상 child 보다 큰 것), Min heap(반대의 경우)

이런 Heap은 중간에 빈 공간이 없기 때문에 일반적으로 array로 편리하게 나타낼 수 있다. [1]에 root를 넣으면, parent[i] = [i/2], left child = 2i, right child = 2i+1 라는 index 관계로 포인터 없이도 편리하게 나타낼 수 있다.

만약 heap element의 크기가 바뀌어 max heap을 지키지 못할 경우, max-heapify 를 통해 다시 이 성질을 만족하게 만들 수 있다. 이 heap의 조건을 만족하지 않는 A[i]의 element를 child와 parent의 크기를 비교하고, 가장 큰 것과 parent를 선택하여 서로의 위치를 교환하는 floating down 과정을 통해 이루어진다.
이런 heap의 level은 총 log(n)개가 되므로 max-heapify 함수의 time complexity는 O(logn)이 된다. (각 parent & child를 비교하는 것은 O(1)이고, 이 과정이 최대 log n번 시행됨)

Build max-heap : 어떤 unsorted array가 주어질 때 해당 array로 heap을 만들고, 중간부터 Max-heapify function을 적용하여 bottom-up 방식으로(개수/2에서 1로 떨어질 때 까지) sorting을 진행하면 된다. (leaf node는 이미 max heap을 지키고 있고, leaf의 수는 전체 node의 수의 절반이므로 중간부터 해당 함수를 적용하면 된다.)

상위 노드의 경우, max property가 지켜지지 않을 때 max-heapify를 recursively call 하여 전체 트리를 sort할 수 있다.
이 때 max heapify는 O(logn)이고 전체 n/2번 시행하므로 전체 time complexity는 O(nlogn)이 된다.
그러나 중간 트리의 경우, 높이는 전체 트리의 최대 높이인 logn이 아니다. 따라서 O(nlogn)은 asymptotically tight bound라고 할 수 없다. (대부분 sub tree의 높이는 log n보다 훨씬 작으므로)

이를 수정하려면 각 level의 최대 노드 수와 해당 level에서 max heapify의 time complexity를 곱한 것을 big O로 나타내어야 한다. n개의 element가 있는 트리에서 level h의 최대 노드 개수는 n/2^(h+1)이 되고, level h의 max heapify time complexity를 O(h)라 할 때, 이를 0부터 logn까지 모두 더하면 해당 값이 전체의 time complexity가 된다.

이를 정리하면 O(n sigma(h/2^h)) 가 되고, n이 무한정 커질 때 h/2^h의 무한 급수 합은 상수가 되므로 max-heap build의 time complexity는 O(n)이 된다.

Heap sort는 주어진 array에 대해 이런 과정을 통해 sort한다. 전체 정렬은 주어진 array를 max heap build 후 max/min 인 root를 pop하고, 반복적으로 n번의 heapify 함수를 call하여 heap을 재정렬 하여 root를 pop하는 방식으로 진행되므로 O(n) + O(n) * O(logn)=O(nlogn) 의 time complexity를 가진다.

이 때 in-place에서 정렬이 이루어지기는 하지만, (pop은 min heap이라고 할 때 last leaf node와 위치를 바꾸는 것으로 구현된다) 같은 크기의 element가 있더라도 각 iteration에서 root가 pop될 때 어느 것이 먼저 root로 올라가 pop되고 정렬될 지 알 수 없으므로 stable하지 않다.

또한 만약 pop한 값을 leaf와 교환하지 않는다면, CBT의 조건을 만족하지 않는다. (가장 큰 것을 뽑아 root로 갖다 놓으면 해당 빈공간이 채워지지 않는다)

* in-place & stability는 정렬의 중요한 특성이지만, 이들을 만족한다고 반드시 다른 방법보다 우수하지는 않다. 메모리 공간이 충분하고, 빠른 정렬이 중요할 경우, quick sort가 많이 사용되는 것 처럼 주어진 condition에 따라 적절한 방법을 찾는 것이 좋다.
Priority Queue (ADT)
element를 priority에 따라 정렬하여 놓은 자료구조. FIFO 규칙을 따르는 일반 큐와 다르게, 저장된 원소들이 우선순위에 따라 출력된다. 따라서 priority queue는 입력 순서 =/= 출력 순서이다.
이는 스케쥴링, 데이터 압축, spanning tree, selection problem 등에 사용할 수 있다.

이는 여러 방법으로 구현될 수 있지만 Heap을 사용하여 구현하는 것이 가장 효율적이고 많이 사용된다.
heap으로 priority queue를 구현할 때 사용하는 함수들은 Get_max, extract_max, Inc_key, insert .. 등이 있다.

- Get_max (O(1)) : root에 있는 우선순위가 가장 높은 값을 리턴한다.
- Extract_max( = delete, O(logn)) : 앞서 heap 정렬과 동일하게 root를 제거한 후 last leaf node를 root로 올리고 max-heapify를 반복적으로 불러 heap의 성질을 만족하게 하는 것.

- Increase_key(O(logn)) : 어떤 원소의 key 값을 증가시켜 제자리를 찾게 하는 것. 상기의 max-heapify와 달리, 아래에 있는 원소를 위로 올릴 때 사용함. 따라서 기존의 key 값이 증가 되었을 때만 호출됨. (만약 값이 줄어들 경우, max-heapify를 호출하여 위에 부터 아래로 내려가며 정렬가능함)
자신과 부모 원소의 키를 비교하여 자신이 더 크다면 위치를 바꾼다. 이 과정을 자신이 부모보다 작을 때 까지 반복하면 다시 heap property를 만족할 수 있다.

- Insertion (O(logn)) : 전체 queue에 새 원소를 삽입하는 경우. 이는 새로운 last leaf node로 해당 원소를 넣고, 상기의 increase_key를 호출하면 올바른 위치에 넣을 수 있다.