作者DJWS (...)
看板Prob_Solve
标题Re: [问题] 有关binomial heap的find min的复杂度
时间Thu Nov 30 05:11:19 2017
※ 引述《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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1511989884.A.E17.html
※ 编辑: DJWS (118.167.24.34), 11/30/2017 05:17:15
1F：推 LPH66: 我不同意 BST 可以取代 heap; 就拿这题的 binomial heap 11/30 09:12
2F：→ LPH66: 来说, 它提供了 O(log n) 合并两个 heap 的操作 11/30 09:12
3F：→ LPH66: 这是 BST 无法达成的 11/30 09:13
4F：→ LPH66: 另外实务上没人用这句话我想打个问号 11/30 09:16
5F：→ LPH66: priority queue 这种资料结构就我所知底层都是 heap 11/30 09:17
6F：→ LPH66: 甚至 C++ STL 有 make_heap push_heap pop_heap sort_heap 11/30 09:18
7F：→ LPH66: 这都是标准的 binary heap 的操作 11/30 09:18
8F：推 hcsoso: 不过的确就算以学习理论的角度而言, binomial跟Fibonacci 11/30 12:26
9F：→ hcsoso: heaps为了达成deterministic而使证明复杂的代价太大了. 11/30 12:27
10F：→ hcsoso: 稍微引入一点随机性就可以教treap了, 更别说它跟quicksort 11/30 12:28
11F：→ hcsoso: 的紧密关联... 11/30 12:28
12F：→ DJWS: @LPH66 合并两个heap，现实世界哪里在使用，请你举个实例 11/30 18:14
13F：→ DJWS: 有一种 bst 叫做 splay tree，合并操作均摊 O(log n) 11/30 18:29
^^^^^^^^ 错了 当我没说 XD
14F：推 pr3pony: binary heap 常数会比 bst 小吧 11/30 23:22
15F：→ pr3pony: 我觉得这样就算有实用价值了 11/30 23:23
16F：→ DJWS: 楼上可能不知道"常数"是中国竞赛选手自创词汇 工程师讨论 12/01 04:31
17F：→ DJWS: 这种事情时所用的词汇叫做benchmark 12/01 04:31
18F：→ DJWS: 另外 除了程式语言内建的binary heap以外 真实世界哪里在 12/01 04:38
19F：→ DJWS: 使用binary heap 欢迎大家举个实例 12/01 04:38
※ 编辑: DJWS (118.167.31.208), 12/01/2017 06:03:51
20F：推 pr3pony: constant factor 这词演算法课本也有提到 12/01 10:05
我记下来了 谢谢
21F：→ pr3pony: 我有找到 splay tree union 均摊 O(log n) 的论文耶 12/01 10:09
23F：→ DJWS: binomial heap 总共 O(log n) splay tree 总共 O(n log n) 12/01 17:40
24F：→ DJWS: 虽然均摊 O(log n)，但是根本就没有比较意义，所以当我没说 12/01 17:42
※ 编辑: DJWS (220.137.8.154), 12/01/2017 17:43:22
25F：推 oToToT: binary search tree跟heap写起来难度差那麽多... 12/09 00:35
26F：→ DJWS: compiler = 100 bst = 2 heap = 1 似乎是比较难没错啦 12/09 07:33
27F：推 Arton0306: 我做的是eda中physical design里面的p&r tool 01/02 23:35
28F：→ Arton0306: 我们的code就有heap 而且是自己写的 01/02 23:36
29F：→ DJWS: 那请教你，输入资料数量多大？ 01/12 15:04
30F：→ DJWS: 还有就是，是什麽任务需要即时得知最小值？ 01/12 15:07