Heapsort 2

Build max heap correction proof

Loop Invariant

복습)
Initialization : It is true prior to the first iteration of the loop.
Maintenance : If it is true before an iteration of the loop, it remains true before the next iteration.
Termination : When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

---

Build-Max-Heap의 Loop Invariant

At the start of each iteration of the for loop, each node i+1, i+2, ..., n-1, n is the root of a max-heap.

Initialization

• At the start of the for loop, i = floor(A.length/2). Each node i+1, i+2 ... n은 리프노드이므로 자명한 max heap이다.
  -> L.I hold

Maintenance

• L.I에 의해 i의 두 자식들은 max heap이다. max-heapify(A, i)는 i를 루트 노드로 하는 서브트리를 max-heap으로 만들어주며, i+1, i+2, ..., n을 각각 루트노드로 하는 서브트리에 대해 max heap 성질을 유지한다.
• i를 감소시키면 다음 수행을 위한 L.I가 여전히 만족한다. "i, i+1, i+2, ..., n-1, n에 대해 ~"

Termination

• i가 0일 때 종료. 이를 L.I에 넣어보면,
• Each node 1, 2, ..., n is the root of a max-heap이 되며, 이는 node 1을 루트로 하는 서브트리, 즉 전체 트리가 max-heap이라는 뜻이다.
  -> 그러므로 Build-max-heap은 max heap을 만드는 데에 correct algorithm.

---

Simpler Upper Bound

• Build-max-heap 자체가 i = floor(n/2)부터 1까지 순회하므로 O(n), 각 순회마다 O(logn)이 걸리는 Max-Heapify를 콜한다.

Tighter Upper Bound

• Max-Heapify는 트리 높이가 h일 때 O(h)의 시간이 걸린다.
• 높이 h는 전체 노드 n개일 때 floor(log(n))이다.

  height : 그 노드에서 아래로 내려가 리프에 도달하는 가장 긴 경로의 간선 수
  depth : 루트에서부터의 거라. level이라고도 함.
  
  -> 중간에 +1을 넣어서 ceil fn을 벗겨내는 디테일 좋다.

따라서, Build max heap의 upper bound를 더욱 타이트하게 잡아보면
O(nlog(n))에서 O(n)까지 만들 수 있다.

Another Analysis of Building a Heap

Let's assume the tree is Complete binary tree.
그러면 노드의 총 개수 n은 2^h - 1개가 된다.

• 높이가 h인 노드의 개수는 1개이며, 이 노드에서 max heapify는 최악의 경우 h만큼 내려간다.
• 높이가 h-1인 노드의 개수는 2개이며, 이 노드에서는 h-1만큼 내려간다.
  ...
• 이를 식으로 표현해보면
  cost S = h + 2(h-1) + 2^2(h-2) + 2^3*(h-3) + ... + 2^(h-1)*(1) + 2^h*0
  2S = 2h + 2^2(h-1) + 2^3(h-2) + ... + 2^h(1)
  ...
  S = 2*2^(log(n)) - log(n) - 2 <= 2n

Heapsort

1. Build max heap을 통해 max-heap으로 만든다.
2. 최댓값이 항상 root에 있으므로 맨 마지막 원소인 A[n]과 A[1]을 교환한다.
3. Max-heapify(A,1)을 A[1...n-1]까지 수행한다.
4. heap의 사이즈가 2가 될 때까지 1~3 과정 반복.
   -> 어차피 A[1]과 A[2]는 이미 정렬되어있기 때문.

Running time

• Build max heap : O(n)
• Each of the n-1 calls to Max-Heapify takes O(lgn) time.
  -> O(nlgn)

Priority Queue

MAX_HEAP_INCREASE_KEY(A, i, key)
if (key < A[i])
	return "new key is smaller than current key"

A[i] = key
while i > 1 && A[parent(i)] < A[i]
	exchange(A[parent(i)], A[i])
    i = parent(i)

MAX_HEAP_INSERT(A, key)
A.heap-size = A.heap-size + 1
A[heap-size] = -Inf
MAX_HEAP_INCREASE_KEY(A, A.heap-size, key)