从Wikipedia
中对二叉堆sift-up
的定义来看,也称为up-heap
操作,sift-down
称为down-heap
.
所以在堆(完全二叉树)中,up
意思是从叶子到根,也down
就是从根到叶子。
但在python中,它似乎正好相反。我对siftup
and的含义感到困惑siftdown
,并且在我第一次使用时被误用。
这是_siftdown
和_siftup
in的 python 版本实现heapq
:
# 'heap' is a heap at all indices >= startpos, except possibly for pos. pos
# is the index of a leaf with a possibly out-of-order value. Restore the
# heap invariant.
def _siftdown(heap, startpos, pos):
newitem = heap[pos]
# Follow the path to the root, moving parents down until finding a place
# newitem fits.
while pos > startpos:
parentpos = (pos - 1) >> 1
parent = heap[parentpos]
if newitem < parent:
heap[pos] = parent
pos = parentpos
continue
break
heap[pos] = newitem
def _siftup(heap, pos):
endpos = len(heap)
startpos = pos
newitem = heap[pos]
# Bubble up the smaller child until hitting a leaf.
childpos = 2*pos + 1 # leftmost child position
while childpos < endpos:
# Set childpos to index of smaller child.
rightpos = childpos + 1
if rightpos < endpos and not heap[childpos] < heap[rightpos]:
childpos = rightpos
# Move the smaller child up.
heap[pos] = heap[childpos]
pos = childpos
childpos = 2*pos + 1
# The leaf at pos is empty now. Put newitem there, and bubble it up
# to its final resting place (by sifting its parents down).
heap[pos] = newitem
_siftdown(heap, startpos, pos)
为什么在python中相反?我已经在 wiki 和其他几篇文章中确认过。有什么我遗漏或误解的吗?
感谢您的阅读,我非常感谢它帮助我。:)