Heap, PQ

1. heap

• binaray tree의 일종으로 complete binary tree 이다.
• binary tree : each paren node can has 1 or 2 children node
• complet binary tree : except the bottom, every level if full of nodes
• heap order : internal node's key >= parent key (min heap_)
• min-heap, max-heap 이 있고 root에 min, max를 항상 둔다 따라서 min is O(1)   
• add, remove 를 위해 last node를 추적한다. 
• How to update the "last" node? : starting from the last node, go up untill a left child or root is reached. If a left child if reached (includes the last node itself), go to the right child. Go down left until a leaf is reached. 
• add, remove is O(logN)(=O(h)) by down-heap bubbling

2. bottom-up construction

• list -> heap
• bottom에 2/n 개 노드부터 시작해서 다음은 4/n노드를 "root" of the subtree로 올려 두고 down-heap을 실행하여 heap 성질을 유지하게 한다. 
• worst case 에서 모든 노드가 많아야 2회씩 관여하게 되고 따라서 O(2n) => O(n)으로 분석한다.

3. PQ 

• priority queue는 key, value의 쌍을 담은 queue로 꺼낼 때 매번 min key 가 우선 나오게 된다. 
• PQ sorting : PQ의 성질을 이용해서 PQ에 넣었다가 꺼내면 sorting 연산을 할 수 있다. 

4. Heap Sort

• PQ with Heap for sorting 
• O(nlogn)
• heap 을 PQ로 사용하여 sorting하면 O(nlogn)으로 정렬을 수행할 수 있다!

(1) heapify : BT -> heap, down-heap from botton, 

(2) heap sort : delete root by swapping with last node, remove last node and down-heap with new root ...