根据维基百科对binary heap的定义,
sift-up
也称为up-heap
操作,sift-down
称为down-heap
。你知道吗
所以在heap(完全二叉树)中,up
表示从叶到根,down
表示从根到叶。你知道吗
但在python中,似乎正好相反。我对siftup
和siftdown
的含义感到困惑,第一次使用时就被误用了。你知道吗
以下是heapq
中_siftdown
和_siftup
的python版本实现:
# '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和其他几篇文章中证实了这一点。我有什么遗漏或误解吗?你知道吗
谢谢你的阅读,我真的很感激你能帮我。:)
查看维基百科页面上的参考资料,我发现:
似乎不同的作者对什么是“上”和“下”有不同的定义。你知道吗
但是,正如@dand在评论中所写的那样,无论如何,你不应该使用这些函数。你知道吗
相关问题 更多 >
编程相关推荐