[理工] 資結 Binomial Heap 性質

看板Grad-ProbAsk作者時間8年前 (2017/07/25 13:01), 8年前編輯推噓3(3推 0噓 8→)
留言11則, 3人參與, 最新討論串1/1
如圖 http://i.imgur.com/qJaoB9y.png
洪毅說 當 Data數 = 2^k 時 則 Binomial Heap 只有1棵 Binomial Tree 這個地方我有個疑問 如果 Data數 = 4 時 不是也可以用 2棵 Binommial Tree (B1) 組成嗎?? 請大大們解惑惹 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.128.148 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1500958910.A.D72.html ※ 編輯: jerry900287 (61.230.128.148), 07/25/2017 13:01:55
→
07/25 13:44, , 1F
2=10。只有一個1,就一顆而已吧，有請其他大大補充
07/25 13:44, 1F
→
07/25 13:45, , 2F
更正 4=100
07/25 13:45, 2F
後來跟同學討論了一下 好像是Binomial Heap 裏頭 高度相同要合併?! 可是我看筆記 Binomial Heap 的定義沒有說 所以不確定是不是這樣?? ※ 編輯: jerry900287 (61.230.128.148), 07/25/2017 13:55:13
→
07/25 14:05, , 3F
合併的意思就像是2進制中進位的意思吧，像是2+2=4
07/25 14:05, 3F
推
07/25 14:27, , 4F
印象中binomial heap有分1.insert後合併2.delete後再合
07/25 14:27, 4F
→
07/25 14:27, , 5F
併，第一種好像叫lazy merge , 若第一種機制使用，你舉
07/25 14:27, 5F
→
07/25 14:27, , 6F
的例子就有可能發生？ 有錯請指正謝謝
07/25 14:27, 6F
推
07/25 14:32, , 7F
更正：就算是第一種機制也不會發生
07/25 14:32, 7F
推
07/25 14:39, , 8F
對不起上面打錯了，第二種才是lazy merge,才有可能出現
07/25 14:39, 8F
→
07/25 14:39, , 9F
你舉的例子
07/25 14:39, 9F
哦哦哦好像是 g大說的 我後來聽完後面 發現說 DS版本的 Binomial Heap 只有在做delete的時候才會去做merge的動作 其他都是用 lazy merge Algo版的 好像是每個動作做完 只要是高度相同都要做merge 所以才不會有我舉的例子 然後 洪毅說 以Algo版的為主 總之感謝兩位大大!!! ※ 編輯: jerry900287 (61.230.128.148), 07/25/2017 15:30:31
→
07/26 15:29, , 10F
洪逸這個部分有些內容是錯的，步驟與時間複雜度等，自
07/26 15:29, 10F
→
07/26 15:29, , 11F
行去查驗資演兩本聖經本做整理會比較保險
07/26 15:29, 11F
!!!!!! 是歐 好 我翻翻看 感謝! ※ 編輯: jerry900287 (61.230.132.209), 07/27/2017 12:19:35
‣ 更多 jerry900287 的文章
文章代碼(AID): #1PTj2-ro (Grad-ProbAsk)