请问到底是sift down 还是shift down

Question

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

Answer 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这个词，比如算法导论中：

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

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

继续加油！：）