CODEWITHSUNDEEP
pythonheapq
ppd0705
ppd0705

Reputation: 11

why need call _siftdown at the end of the func _siftup in python moudle heapq

I am reading the source code of heapq, and found that the _siftup func called _siftdown at last. I think it is a bit redundant. I want to to known that is this really necessary?

I did a test bwtween the two condition, but I did not find any difference between the two condition. the test code is below (the heap_test is a copy of heap and commented the last line of _sifup):

from heapq_test import heapify as heapify_test

import heapq
import random

for _ in range(200000):
    a = [random.randint(0, 30) for _ in range(100)]
    b = a.copy()
    heapify_test(a)
    heapq.heapify(b)
    assert a == b

Upvotes: 1

Views: 154

Answers (2)

Rogers
Rogers

Reputation: 91

The func _siftup is optimized in heapq sourcecode, the implementation in this way that just Bubble up the smaller child until hitting a leaf and _siftdown finnaly can cut the number of comparisions a little than normal way (just _siftup and compare parent with left_child, right_child every time).

Upvotes: 0

rookie
rookie

Reputation: 21

The last _siftdown at _siftup func is necessary. An example helps.

heap = [1,1,1,3,4,5,1]

if you delete the last _siftdown in _siftup and do the heappop() you get [1, 1, 5, 3, 4, 1] which is not a heap.

The last _siftdown is necessary, because the while loop in below code(from the heapq source code) just pick the smaller child but didn't compare the newitem's value with child, so in the last we need a _siftdown. And why the author implement _siftup function in this way? and why it continues to find the smaller child until a leaf is hit in _siftup? you can get these in the author comment above the _siftup function in the source code.

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)

Hope this reply helps you.

Upvotes: 2

Related Questions