priorityqueues-資料下載頁
2025-07-17 16:43本頁面
【正文】 ? 定理 : 對 weightbased leftist tree的任一 internal node x, rightmost(x)為其至任一 external node的路徑中最右邊一條的長度 . 則 rightmost(x)≤ log2(?? ?? +1) ? 證明 (使用歸納法 )請見課本 ? meld, insert, delete的方法如同一般 leftist tree ? 好處 : 第二步驟不用再使用獨(dú)立一個 pass即可完成 BHeap (Binomial Heap) ? 目標(biāo) : ? 1. 支援 insert, delete (min), and meld的動作 ? 2. “平均來說 ” 單一 的 operation可能可以到達(dá) O(1)或 O(log n) ? 跟課本講得不太一樣 ? 參考資料 : ? ? 很讚的動畫 applet ? Binomial Tree長什麼樣子 ? binomial tree的定義 : ? 1. binomial tree of order 0 ?只有單一 node ? 2. binomial tree of order k?一個 root, 自己的 children為 order為 k1, k2, …, 0的 binomial tree們 ? node數(shù)目為 n, ?? = 2?????????? ??2 ??1 ??0 ??3 表示方法 Siblings: Linked List, ordered by tree degree min Binomial Heap長什麼樣子 ? 是 binomial tree組成的 forest ? 1. 每個 tree的任何一 parent node的 key大 (小 )於 child node的key ? 2. 每個 order的 binomial tree只能在這個 forest裡面有一顆或零 棵 ? 條件 2. 使得 n個 node的 binomial heap最多只有 log2 ??+1棵樹 ??1 ??0 ??3 Merge兩棵 order一樣的樹 ? 看 root key誰比較小 ? 小的當(dāng)新的樹的 root ? 大 的接在新的樹的 root下面 2 4 min 2 4 min Merge兩個 heap (Meld) ? 假設(shè)要 merge p和 q兩個 heap ? p和 q各有 order 0K的 binomial tree ? 則開始看 每 個 order (假設(shè)是 i) ? 如果 p和 q中只有一個有 order i的 ? 則直接丟到 merged的 heap ? 否則 的話 , 就把兩個 tree合併 ? 合併後 的 tree, 還有可能跟後面 order比較大的 tree再合併 ? 黑板舉另外一個例子 ? ? O(log n) 5 8 4 ??1 ??0 2 ??0 3 6 7 9 ??2 p q order 0: 都有 2 4 合併的 : order 1: 只有一個 , 但merge過後的也有 5 8 order 2: 只有一個 , 但merge過後的也有 3 6 7 9 Insert amp。 Find minimum ? Insert: ? 使用 merge來 implement ? 當(dāng)作 merge原本的 heap和一個 order 0的 tree(只有一個 node)就好 ? O(log n) ? “平均 來 講 ”可以達(dá)到 O(1)! ? Find minimum: ? 把所有樹的 root key都檢查一遍找到最小的 ? O(log n) ? 或 O(1) 如果有一個 pointer每次都指到最小的 ? (把找的動作在其他 operation做了 ) Delete minimum 假設(shè)這個是最小的 拿掉之後 , 底下的 sub tree也是binomial heap 除了有動到的 tree之外 , 其他的sub tree也是一個 binomial heap Merge O(log n)
化學(xué)相關(guān)推薦
鄂ICP備17016276號-1