Heaps

可以視為Priority Queue的特例（為Priority Queue的子集合）。
註記：height從0層開始。

• Priority Queue ADT
  1.有個entry，為key與value組成的pair，其中value用來擺東西，可能是個複雜的資料，而key則是用來比較大小的東西。
  2.insert(a)
  3.RemoveMin
  4.min()
  5.size()
  6.empty()

• Priority Queue Sorting
  可以將元素插入進Queue中，因為Priority Queue為照優先值排列，所以可以一路拉出元素，達到sorting。
  有各式各樣的implementation，也各自有不一樣的running time。
  1.Unsorted sequence
  進來時隨便放，要出去時，進行selection sort
  -->O(n^2)
  2.Sorted sequence
  剛進來Queue時，先進行selection sort來插入，出去則直接出去
  -->O(n^2)

• Two Paradigm for PQ
  1.PQ via selection sort
  a.insert : O(1)

    -->直接放入Queue的最後方  
  

  b.min/removeMin : O(n)

    -->提出來時，要先經過selection sort  
  

  c.empty/size : O(1)
  2.PQ via insertion sort
  a.insert : O(n)

    -->在插入前，先透過insertion sort選出要插入的最小值  
  

  b.min/removeMin : O(1)

    -->因為已經排序好了，只需要直接提出即可  
  

  c.empty/size : O(1)

  -->所以要處理所有值 : O(n^2)

• Heap
  為一個binary tree，而key存在node中，主要有兩個特點：
  1.Heap Order
  在node中放的key，其key一定≥其parents的key
  key(v) ≥ key(parents(v))
  -->此為min Heap
  2.Complete binary tree
  此tree是滿的，只有最後一層不是
  a.從0~(h-1)層，都有2^h個node
  b.在第h-1層，internal node都會在external node左邊
  c.last node一定在右邊

• Height of Heaps
  Theorem : 若有n個key，則高度為O(logn)
  poof : 2^0 + 2^1 + ... + 2^(h-1) + 1 ≤ n ≤ 2^0 + 2^1 + ... + 2^(h-1) + 2^h

      =>2^h ≤ n ≤ 2^\(h+1\) - 1  
      =>**log\(n+1\) - 1 ≤ h ≤ log\(n\)**
  

• Insertion into a Heap
  過程：
  1.找到last node的位置
  2.將新的值插入
  3.往上看，看heap order有無亂掉，亂掉就整理，持續至整理完

  -->bubble up
  -->O(logn)

• Removal from Heap
  過程：
  1.把last node的值拉上root
  2.從上往下看，慢慢整理

  --> Down-heap bubbling
  -->O(logn)

• Heap complexity
  empty/size : O(1)
  insert : O(logn)
  min : log(1)
  removeMin : O(logn)
  Sorting : O(nlogn)

• 找出要Insert的位置
  過程：
  1.從last node一路往上走，直到碰到left child（or root）
  2.再走到對應的right child
  3.再往下走左子點至最底

  -->It is easy to use vector to build heap

• Vector-based Heap Implementation
  1.若有n個key要存，長度設為n+1（通常第一個不用）
  2.若一個key，其index為i，則左子樹為2i，右子樹為2i+1
  3.找parents時，直接index除以二，無條件捨去
  4.in place：所有操作都在現有的空間中，不用使用到額外的資源

• In-place Heap sort
  1.將vector裡的值排為max-heap
  2.再慢慢輸出

• Merg two heap
  1.假設兩個heap，有個key，利用此key串起兩個heap
  2.因為左右子樹都滿足了heap，所以由root調整

• Bottom-up Heap Construct
  只能用在link-list，其複雜度為O(n)