请稍等 ...
×

采纳答案成功!

向帮助你的同学说点啥吧!感谢那些助人为乐的人

请问到底是sift down 还是shift down

看到本课程里说的写的是sift,之前的课程是shift。请老师确认一下。谢谢。

正在回答 回答被采纳积分+3

1回答

liuyubobobo 2019-04-01 15:46:41

其实这两个词都可以。


如果溯源,应该是sift。wiki百科取得sift。可以参考:https://en.wikipedia.org/wiki/Binary_heap


但是,由于sift和shift拼写很接近,同时,取shift的意思,没什么不妥的(甚至更贴切),所以,很多资料也是使用shift。大家在理解上,不会有歧义。随便举几例:


某大学的教材,使用shift: https://www.cs.wcupa.edu/rkline/ds/heaps.html

一些线上教程使用shift: http://www.codenlearn.com/2016/02/a-simple-heapsort-and-heap-data-structure.html

raywenderlich(一家著名iOS在线教育品牌)的swift算法教程使用shift: https://github.com/raywenderlich/swift-algorithm-club/tree/master/Heap


----------


或许是为了消除这个歧义。很多教材,会避免使用sift/shift的用法。比如大名鼎鼎的算法4,使用的是swim(上浮)和sink(下沉):https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/MaxPQ.java.html


补充一下,之所以使用shift大家觉得没问题,是因为在解释这个操作的时候,一般都会用到shift这个词,比如算法导论中:

https://img.mukewang.com/szimg/5ca1c1070001ea4f12000676.jpg


btw,算法导论也避免了使用sift/shift的问题。但是算法导论取的名字非常不好,我个人不建议使用,比如用max-heapify表示下沉,完全没有体现出下沉这个动作。


结论:如果你对此特别在意,请使用sift,这应该是原始论文所用的名称;但其实,无所谓,完全不影响交流,也不会有人笑话你的。:)


继续加油!:)


0 回复 有任何疑惑可以回复我~
问题已解决,确定采纳
还有疑问,暂不采纳
意见反馈 帮助中心 APP下载
官方微信