推 seanwu:selection tree ? 11/17 00:17
→ a127a127:樓上強者 //原來原本那些node是虛擬的啊@@a 11/17 00:35
→ a127a127: //難怪當初看到的時候覺得怪怪的XD 11/17 00:36
推 DJWS:winner tree 11/17 21:52
推 command:喔喔! 好方法! 感謝感謝! 11/18 12:03
┌─┐
│ │
└─┘
／ ＼
／ ＼
┌─┐ ┌─┐
│ │ │ │
└─┘ └─┘
／ ＼ ／ ＼
┌─┐ ┌─┐ ┌─┐ ┌─┐
│ │ │ │ │ │ │ │
├─┤ ├─┤ ├─┤ ├─┤
│ │ │ │ │ │ │ │
上半是個heap，下面是m個array。
每次取最小值的時候，把root拿走。
然後一路把比較小的往上拿，花剛好lg(m)的時間。
總共取n次就好了。
時間複雜度Θ(m+n*lg(m))
空間複雜度Θ(m)
跟array拿值次數Θ(m+n)
不知道這樣講你看不看得懂 XD。
（它有個名字，不過我忘了@@a。）
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 115.43.146.11