Microsoft PowerPoint - lecture14.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - lecture14.pptx"

本尹
5 years ago
Views:

1 PRIORITY QUEUES Michael Tsai 00//8

2 Outline Dynamic hashing Priority Queue 的種類 DEPQ 的用途 Leftist Tree Binomial Heaps

3 Dynamic hashing 觀察 : 當 n/b 比較大以後, O() 就開始崩壞 ( 往 O(n) 方向移動 ) 應變 : 所以要隨時觀察 n/b, 當它大過某一個 threshold 時就把 hash table 變大觀察 : 把 hash table 變大的時候, 需要把小 hash table 的東西通通倒出來, 算出每一個 pair 在大 hash table 的位置然後重新放進大 hash table 有個可憐鬼做 insert 正好碰到應該 hash table rebuild 的時候, 他就會等非常非常久. T_T

4 Dynamic hashing 目標 : 重建的時候, 不要一次把所以重建的事情都做完或許, 留一些之後慢慢做? 每個 operation 的時間都要合理又叫做 extendible hashing

5 例子 k h(k) A A B B 0 00 C 0 00 C 0 00 C3 0 0 C5 0 0 h(k,i)=bits 0 i of h(k) Example: h(a0,)=0 h(a,3)=00= h(b,4)=00=9

6 Dynamic hashing using directories directory depth= number of bits of the index of the hash table A0, B0 A, B C C3 Insert C5 h(c5, )=0= C5, overflow we increase d by until not all h(k,d) of the keys in the cell are the same 動腦時間 : 如果原本的要加入 C 呢? 如果第二步驟後加入 A4 呢? 答案 : p A0, B0 A, B C C3 C5 k h(k) A A B B 0 00 C 0 00 C 0 00 C3 0 0 C5 0 0

7 Dynamic hashing using directories 為什麼比較快? 只需要處理 overflow 的櫃子如果把 directory 放在記憶體, 而櫃子資料放在硬碟則 search 只需要讀一次硬碟 insert 最多需要讀一次硬碟 ( 讀資料, 發現 overflow 了 ), 寫兩次硬碟 ( 寫兩個新的櫃子 ) 當要把 hash table 變兩倍大時, 不需要碰硬碟 ( 只有改 directory)

8 Directoryless Dynamic hashing 假設 hash table 很大, 但是我們不想一開始就整個開來用 (initialization 會花很大 ) 用兩個變數來控制的 hash table 大小 : r, q hash table 開啟的地方為 0, 之間 q~ 之間使用 h(k,r) 0~q 及 ~ 之間使用 h(k,r+) r=, q=

9 Directoryless Dynamic hashing 每次輸入的時候, 如果現在這個櫃子滿了則開一個新的櫃子 : 原本 q 櫃子裡面的東西用 h(k,r+) 分到 q 和兩櫃子裡注意有可能還是沒有解決問題多出來的暫時用 chain 掛在櫃子下面 000 A0 00 B4, A0 0 A, B5 C5 0 A, B5 insert C5, full 0 C 0 C C3 C3 00 B4 r=, q=0 r=, q= 問 : 再加入 C 呢? ( 課本 p 45) k h(k) A A B B5 0 0 C 0 00 C 0 00 C3 0 0 C5 0 0

10 複習 : Priority queue 的 operations A. 看 ( 找到 )queue 裡面 priority 最小 ( 或最大 ) 的 element B. 插入一個 element 到 queue 裡面 C. 拿掉 (delete)queue 裡面 priority 最小 ( 或最大 ) 的 element 之前用 max or min heap A=O() B=O(log n) C=O(log n)

11 其他 priority queue 的種類 Meldable priority queue: 除了原本三個 operation 還支援一個 operation 可以把兩個 priority queue 合併有什麼用途? Double ended: 可以拿最大也可以拿最小的 ( 原本的為 single ended) 支援下面的 operations A. 看 ( 找到 )queue 裡面 priority 最小的 element B. 看 ( 找到 )queue 裡面 priority 最大的 element C. 插入一個 element 到 queue 裡面 D. 拿掉 (delete)queue 裡面 priority 最小的 element E. 拿掉 (delete)queue 裡面 priority 最大的 element

12 DEPQ 的用途 () DEPQ=Double Ended Priority Queue 用來 implement network buffer PCMAN Mozilla Firefox World of Warcraft utorrent. 網路印表機驅動程式狀況一 : 網路 busy, 可是 buffer 已經滿了, 必須丟掉東西取出 priority 最低的封包丟掉 DEPQ!! 網路卡驅動程式的 buffer 網路實體線路狀況二 : 網路目前 idle, 必須選出下一個要傳到網路上的封包取出 priority 最高的封包傳出

13 DEPQ 的用途 (): External sorting External sorting 的適用時機 : 無法全部丟入主記憶體 ( 部分要放在慢速儲存媒體 ) 使用 DEPQ 來 implement quick sort 的變種. 每次再從待 sorting 的數字們中取一個新的數字 A. 假設此時 DEPQ 中具 max/min priority 的數字分別為 B 與 S. b. 若 A<S, 則將 A 放到左邊一堆待 sorting 的數字們 DEPQ. 從待 sorting 的數字中不斷拿數字放入 DEPQ 直到放滿主記憶體為止 a. 若 A>B, 則將 A 放到右邊一堆 c. 若, 則將 DEPQ 中 B 拿出丟到右邊 ( 或者將 DEPQ 中 S 拿出丟到左邊 ), 並將 A 放入 DEPQ 左邊一堆 : 都比 DEPQ 中的數字小右邊一堆 : 都比 DEPQ 中的數字大

14 DEPQ 的用途 (): External sorting DEPQ 3. 將待 sorting 之數字堆拿空以後, 剩下 DEPQ 的數字, 依序拿出 priority 最高的, 放入中間一堆中間一堆 : 從原本 DEPQ 放出來的左邊一堆 : 都比中間一堆的數字小右邊一堆 : 都比中間一堆的數字大 4. 中間一堆已排好, 遞迴呼叫繼續將左邊一堆及右邊一堆排好.

15 Meldable Priority Queue: Leftist tree Heap: 要花多少時間結合兩個 heap? 把兩個 heap 都當作沒有排過直接重新建一個大 heap 用從一個 array 建成一個 heap 的方法 ( 課本 section 7.6 heapsort) 需要 O(n) 目標 : meld, insert, delete=o(log n) find=o()

16 Extended Binary Tree A A 對應 B C B C D E F D E F Binary Tree Extended Binary Tree : internal nodes : external nodes

17 Leftist tree 的一些定義 Shortest(x): 從某個 extended tree 的 node 走到任一個 external node 的距離可以用遞迴定義 : Shortest(x)= a. 0, if x 是 external node b. + min{shortest(leftchild(x)), shortest(rightchild(x))}, if x 是 internal node 定義 : A leftist tree is a binary tree such that if it is not empty, then shortest(leftchild(x)) shortest(rightchild(x)), for every internal node x.

18 例子 : 這是 leftist tree 嗎? A B C shortest(leftchild(c))=0 shortest(rightchild(c))= D E F

19 一些性質假設 r 為 leftist tree 的 root, n 為 internal nodes 個數.. 從 root 到任何一 external node 的路徑中最右邊的一條, 為最短. 其長度為 shortest(r) log 為什麼?. shortest(r) 層內沒有 external nodes.. 由定義得知左邊的路徑一定比右邊的路徑長.

20 Min leftist tree Min leftist tree: 一個所有某 node 的 key 值永遠比它的小孩 key 值小的 leftist tree

21 Insert & Delete by Melding Insert(a, tree b): 創造一個只有 a 的 min leftist tree, 然後 meld(a,b). remove root node r tree b Meld(a,b) a left child s tree right child s tree Meld(leftChild(root), rightchild(root)) Delete(tree b): Meld(leftChild(root(b)), rightchild(root(b)))

22 Melding process Example Step : 把兩棵樹合併並確定 parent 的 key 大於 children 的 key is smaller than 5 add to the new tree

23 Melding process Example Step : 把兩棵樹合併並確定 parent 的 key 大於 children 的 key 5 is smaller than 50 add to the new tree

24 Melding process Example Step : 把兩棵樹合併並確定 parent 的 key 大於 children 的 key 8 is smaller than 50 add to the new tree

25 Melding process Example Step : 把兩棵樹合併並確定 parent 的 key 大於 children 的 key add to the new tree

26 Melding process Example Step : 把兩棵樹合併並確定 parent 的 key 大於 children 的 key

27 Melding process Example Step : 沿著剛剛右邊一條路線的 root, 確定所有的 shortest(left) shortest(right) 7 5 not ok ok 50 ok

28 Melding process Example Step : 沿著剛剛右邊一條路線的 root, 確定所有的 shortest(left) shortest(right) not ok

29 Melding process Example Step : 沿著剛剛右邊一條路線的 root, 確定所有的 shortest(left) shortest(right)

30 那要花多少時間呢? Meld operation = O(??) 兩個 operation 都只要花走右邊路徑長度的時間右邊路徑長度都是最短的 Worst case: balanced binary tree 所以所花時間為 O(log n)

31 變形 : Weight based leftist tree w(x): node 的 weight w(x)= 以 x 當作 root 的 subtree 裡面 internal node 的數目如果 x 是 external node, 則 w(x)=0 w(x) 遞迴定義 : w(x)=+w(leftchild(x))+w(rightchild(x)) Weight based Leftist Tree 定義 : 對每一個 internal node x, w(leftchild(x)) w(rightchild(x)). 其中又可以有 Max or min weight based leftist tree (parent key 值大於 children key 值 )

32 Weight based leftist tree 定理 : 對 weight based leftist tree 的任一 internal node x, rightmost(x) 為其至任一 external node 的路徑中最右邊一條的長度. 則 rightmost(x) log 證明 ( 使用歸納法 ) 請見課本 p.43 meld, insert, delete 的方法如同一般 leftist tree 好處 : 第二步驟不用再使用獨立一個 pass 即可完成

33 B Heap (Binomial Heap) 目標 :. 支援 insert, delete (min), and meld 的動作. 平均來說單一的 operation 可能可以到達 O() 或 O(log n) 跟課本講得不太一樣參考資料 : 很讚的動畫 applet

34 Binomial Tree 長什麼樣子 binomial tree 的定義 :. binomial tree of order 0 只有單一 node. binomial tree of order k 一個 root, 自己的 children 為 order 為 k, k,, 0 的 binomial tree 們 node 數目為 n,

35 表示方法 min Siblings: Linked List, ordered by tree degree

36 Binomial Heap 長什麼樣子是 binomial tree 組成的 forest. 每個 tree 的任何一 parent node 的 key 大 ( 小 ) 於 child node 的 key. 每個 order 的 binomial tree 只能在這個 forest 裡面有一顆或零棵條件. 使得 n 個 node 的 binomial heap 最多只有 log + 棵樹

37 Merge 兩棵 order 一樣的樹看 root key 誰比較小小的當新的樹的 root 大的接在新的樹的 root 下面 min min 4 4

38 Merge 兩個 heap (Meld) 假設要 merge p 和 q 兩個 heap p 和 q 各有 order 0 K 的 binomial tree 則開始看每個 order ( 假設是 i) 如果 p 和 q 中只有一個有 order i 的則直接丟到 merged 的 heap 否則的話, 就把兩個 tree 合併合併後的 tree, 還有可能跟後面 order 比較大的 tree 再合併黑板舉另外一個例子 O(log n) 合併的 : 8 5 p q 4 order 0: 都有 order : 只有一個, 但 merge 過後的也有 order : 只有一個, 但 merge 過後的也有

39 Insert & Find minimum Insert: 使用 merge 來 implement 當作 merge 原本的 heap 和一個 order 0 的 tree( 只有一個 node) 就好 O(log n) 平均來講可以達到 O()! Find minimum: 把所有樹的 root key 都檢查一遍找到最小的 O(log n) 或 O() 如果有一個 pointer 每次都指到最小的 ( 把找的動作在其他 operation 做了 )

40 Delete minimum 除了有動到的 tree 之外, 其他的 sub tree 也是一個 binomial heap 假設這個是最小的 Merge O(log n) 拿掉之後, 底下的 sub tree 也是 binomial heap

Hashing

Hashing HASHING Michael Tsai 2012/05/29 有沒有一種天方夜壇 Insert (key, data) Search Delete =O(1) 神秘的資料結構 Hint: 以空間換取時間概念很多很多有編號的櫃子問 : 菜瓜布的資料去哪找? ( 菜瓜布, 資料 ) 管理員管理員 : 菜瓜布對應到 1028 號櫃子 1028 如果箱子夠多, 則花費在一個箱子裡面尋找的時間