siftdown函數的實現是否違反堆的形式定義？

Question

我想了解堆的實現現在，我看着python的heapq模塊。
https://github.com/python-git/python/blob/master/Lib/heapq.py
Line236是siftdown的代碼的開始，奇怪的是，它看起來像是一個siftup，因爲它在堆數組的最後一個元素上添加了一個newitem，並嘗試將最後一個元素向上移動到它的正確位置。

while pos > startpos: 
     parentpos = (pos - 1) >> 1 
     parent = heap[parentpos] 
     if newitem < parent: 
      heap[pos] = parent 
      pos = parentpos 
      continue 
     break 

它降低了當前位置到（POS-1）// 2，最後的POS索引可以去索引0 所以它看起來像一個siftup給我。我誤解了什麼嗎？

Answer 1

這只是一個命名衝突。他們所謂的「篩選」正朝着樹葉篩選。也許這個想法是，在一個小堆裏，大的物品向上移動到葉子上。

他們的「siftdown」向根部移動。

它與我們通常將電腦人們認爲是樹的方式顛倒，但它是一致的。如果你描繪一棵物理樹 - 在院子裏生長的東西和在秋天落下的葉子，我必須耙掉並處理。