Why is heapq.heapify so fast?

Question

I have tried to reimplement heapify method in order to use _siftup and _siftdown for updating or deleting any nodes in the heap and maintaining a time complexity of O(log(n)).

I did some effort for optimizing my code, But they proved to be worse compared to that of heapq.heapify (in terms of the total time taken). So I have decided to look into source code. and compared copied code with the modules ones.

# 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)


def heapify(x):
    """Transform list into a heap, in-place, in O(len(x)) time."""
    n = len(x)
    # Transform bottom-up.  The largest index there's any point to looking at
    # is the largest with a child index in-range, so must have 2*i + 1 < n,
    # or i < (n-1)/2.  If n is even = 2*j, this is (2*j-1)/2 = j-1/2 so
    # j-1 is the largest, which is n//2 - 1.  If n is odd = 2*j+1, this is
    # (2*j+1-1)/2 = j so j-1 is the largest, and that's again n//2-1.
    for i in reversed(range(n//2)):
        _siftup(x, i)

a = list(reversed(range(1000000)))
b = a.copy()

import heapq

import time

cp1 = time.time()
heapq.heapify(a)
cp2 = time.time()
heapify(b)
cp3 = time.time()

print(a == b)
print(cp3 - cp2, cp2 - cp1)

And i found always cp3 - cp2 >= cp2 - cp1 and not same , heapify took more time than heapq.heaify even though both were same. And in some case heapify took 3 seconds and heapq.heapify took 0.1 seconds

heapq.heapfy module executes faster than the same heapify they only differ through import.

please let me know the reason, I am sorry if I made some silly mistakes.

Answer 1

The heapify from the heapq module is actually a built-in function:

>>> import heapq
>>> heapq
<module 'heapq' from 'python3.9/heapq.py'>
>>> heapq.heapify
<built-in function heapify>

help(heapq.heapify) says:

Help on built-in function heapify in module _heapq...

So it's actually importing the built-in module _heapq and thus running C code, not Python.

If you scroll the heapq.py code further, you'll see this:

# If available, use C implementation
try:
    from _heapq import *
except ImportError:
    pass

This will overwrite functions like heapify with their C implementations. For instance, _heapq.heapify is here.