Implementieren von Siftdown-Funktion verletzt Heap formale Definition?

Question

Ich versuche, die Implementierung von Heap jetzt zu verstehen, und ich schaue in Heapq-Modul von Python.

Line236 ist der Anfang des Codes von siftdown, das seltsame Ding ist, es sieht wie ein Siftup für mich aus, weil es ein neues Element auf dem letzten Element des Heap-Arrays hinzufügt und versucht, das letzte Element nach oben zu verschieben seine richtige Position.

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

Es reduziert den Index der aktuellen Position (pos-1) // 2 und schließlich der pos zum Index kann 0. So ist es wie ein siftup mir aussieht. Versteh ich etwas falsch?

Answer 1

Es ist nur ein Nomenklaturkonflikt. Was sie "Siftup" nennen, ist das Sichten auf die Blätter. Vielleicht ist der Gedanke, dass sich in einem Min-Heap größere Gegenstände "nach oben" zu den Blättern bewegen.

Ihr "siftdown" bewegt sich in Richtung der Wurzel.

Es ist auf den Kopf gestellt von dem, was wir Computermenschen normalerweise (?) Als Baum betrachten, aber es ist konsistent. Und es macht Sinn, wenn du dir einen physischen Baum bildest - das Ding, das auf dem Hof ​​wächst und im Herbst Blätter fallen lässt, die ich aufsammeln und entsorgen muss.