Re: [問題] 有關binomial heap的find min的複雜度

[DJWS (...)]

※ 引述《JinSha ( )》之銘言：
: 所以若是遇到問的問binomial heap的find min的複雜度時，
: 有的地方會說O(log n)，有的地方會說O(1)
: 比方說
: https://en.wikipedia.org/wiki/Binomial_heap#cite_note-amortized-9
: http://www.growingwiththeweb.com/data-structures/binomial-heap/overview/
: 這兩的地方是說O(log n)

https://en.wikipedia.org/wiki/Binomial_heap#Find_minimum

To find the minimum element of the heap, find the minimum among the roots of
the binomial trees. This can again be done easily in O(log n) time, as there
are just O(log n) trees and hence roots to examine.

By using a pointer to the binomial tree that contains the minimum element,
the time for this operation can be reduced to O(1). The pointer must be
updated when performing any operation other than Find minimum. This can be
done in O(log n) without raising the running time of any operation.

也就是說，原本是 O(log n)，但是可以取巧改進到 O(1)。

題外話：
實務上沒有人使用 binomial heap，甚至實務上沒有人使用任何一種 heap。
同樣的事情可以用 binary search tree 做到。(除了合併操作)(感謝LPH66指正)
教科書會寫 binomial heap，是因為作者覺得這很有特色，具有一咪咪理論上的價值。
教授上課會教 binomial heap，是因為臺灣教授的水平，僅止於複誦教科書。
研究所考試會考 binomial heap，是因為教授要貫徹上意，達成我國愚民教育的方針。
至於正確答案應該要填 O(1) 還是 O(log n)，其實是教授說了算，他們爽就好。
反正現實世界沒有人在用。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.167.24.34
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1511989884.A.E17.html
※ 編輯: DJWS (118.167.24.34), 11/30/2017 05:17:15
推 LPH66: 我不同意 BST 可以取代 heap; 就拿這題的 binomial heap
→ LPH66: 來說, 它提供了 O(log n) 合併兩個 heap 的操作
→ LPH66: 這是 BST 無法達成的
→ LPH66: 另外實務上沒人用這句話我想打個問號
→ LPH66: priority queue 這種資料結構就我所知底層都是 heap
→ LPH66: 甚至 C++ STL 有 make_heap push_heap pop_heap sort_heap
→ LPH66: 這都是標準的 binary heap 的操作
推 hcsoso: 不過的確就算以學習理論的角度而言, binomial跟Fibonacci
→ hcsoso: heaps為了達成deterministic而使證明複雜的代價太大了.
→ hcsoso: 稍微引入一點隨機性就可以教treap了, 更別說它跟quicksort
→ hcsoso: 的緊密關聯...
→ DJWS: @LPH66 合併兩個heap，現實世界哪裡在使用，請你舉個實例
→ DJWS: 有一種 bst 叫做 splay tree，合併操作均攤 O(log n)
                                                  ^^^^^^^^ 錯了 當我沒說 XD
推 pr3pony: binary heap 常數會比 bst 小吧
→ pr3pony: 我覺得這樣就算有實用價值了
→ DJWS: 樓上可能不知道"常數"是中國競賽選手自創詞彙  工程師討論
→ DJWS: 這種事情時所用的詞彙叫做benchmark
→ DJWS: 另外  除了程式語言內建的binary heap以外  真實世界哪裡在
→ DJWS: 使用binary heap  歡迎大家舉個實例
※ 編輯: DJWS (118.167.31.208), 12/01/2017 06:03:51
推 pr3pony: constant factor 這詞演算法課本也有提到
                                我記下來了  謝謝
→ pr3pony: 我有找到 splay tree union 均攤 O(log n) 的論文耶
→ pr3pony: https://goo.gl/vSsAu5
→ DJWS: binomial heap 總共 O(log n)  splay tree 總共 O(n log n)
→ DJWS: 雖然均攤 O(log n)，但是根本就沒有比較意義，所以當我沒說
※ 編輯: DJWS (220.137.8.154), 12/01/2017 17:43:22
推 oToToT: binary search tree跟heap寫起來難度差那麼多...
→ DJWS: compiler = 100  bst = 2  heap = 1  似乎是比較難沒錯啦
推 Arton0306: 我做的是eda中physical design裡面的p&r tool
→ Arton0306: 我們的code就有heap 而且是自己寫的
→ DJWS: 那請教你，輸入資料數量多大？
→ DJWS: 還有就是，是什麼任務需要即時得知最小值？