[Introduction To Algorithms] 第六堂: Heapsort

開始上演算法的應用了，講的是 HeapSort，Heapsort有兩個用途

• 排序
• Priority Queues 的實作

前面屬於資料結構的部分，Heap 的定義、性質、如何 maintain heap (heapify)

接下來討論到 Heapify 的 Running time 

書上直覺地導出上下界。 老師也補充了用 recurrence 的算法。  p.7 注意不能用θ表示。

再來才是分析 worst case(演算法分析要精確)

接下來談到 heap 的建立，也分析了 running time  p.11 ~ p.15

再來就是分析 Heapsort algo....

這裡用到一個 lemma 推導出 n 的 nodes 時，heap 的高度，原理很簡單，自己可以推出來。

這裡老師花了蠻多時間講，列出幾個點

1.  O(0) 的意義
2. 用到之前 rule of sum 等 theorem

我下課問了一下老師，為何可以 remove floor and ceiling = =" 這之前才學過 smooth fun 可以去 floor and ceiling !!

這段老師也強調了一下，畫線的那一段書上沒有說明，老師主要補充， lgn+1到 ∞ 那一段不是"master"。

heap build 分析完後，Heapsort 分析就很簡單了。 p.15~p.17

Priority Queue 不管是 max 還是 min 本質上都一樣。
接下來要分析 Priority Queue 運算的時間。
p.18~p.19

注意 Heap-Increase-Key 這個運算，他其實只要θ(i) 就可以了但是對於整體而言，我們只關心 input size 是 n 時，複雜度是多少，因此θ(n)比較符合需求。












掰!!