Почему _siftup и _siftdown в Python противоположны? - PullRequest
Новая
       43

Почему _siftup и _siftdown в Python противоположны?

0 голосов
/ 27 марта 2019

Из определения двоичной кучи в Википедии, sift-up также называется up-heap операцией, а sift-down называется down-heap.

Таким образом, в куче (полное двоичное дерево) up означает от листа к корню, а down означает от корня до листа.

Но в питоне это выглядит как раз наоборот. Меня смущают значения siftup и siftdown, и я неправильно использую их в первый раз.

Вот реализация Python версии _siftdown и _siftup в 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)

Почему наоборот в питоне? Я подтвердил в вики и нескольких других статьях. Я что-то упускаю или неправильно понимаю?

Спасибо за чтение, я действительно ценю это, чтобы выручить меня. :)

1 Ответ

2 голосов
/ 27 марта 2019

Глядя на ссылки на странице Википедии, я заметил это:

Обратите внимание, что в этой статье используется оригинальная терминология Флойда "siftup" для того, что сейчас называется просеиванием вниз .

Казалось бы, разные авторы имеют разные ссылки на то, что "вверх" и "вниз".

Но, как пишет @Dan D в комментарии, вы не должныв любом случае использовать эти функции.

...