※ 引述《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),其实是教授说了算,他们爽就好。
反正现实世界没有人在用。