CODEWITHSUNDEEP
python-3.xheap
etang
etang

Reputation: 538

Why heapq.heappush is an O(log n) operation?

import heapq  
  
minHeap = [4, 7, 2, 8, 1, 3]  
heapq.heapify(minHeap) # O(n log n) operation
print(minHeap) # [1, 4, 2, 8, 7, 3]  
 
heapq.heappush(minHeap, 1) # O(log n) operation?
print(minHeap) # [1, 4, 1, 8, 7, 3, 2]

I guess heapq.heappush will create a new array and assigned to minHeap. If this is correct, wouldn't this operation be an O(n) operation instead of O(log n)?

Upvotes: 0

Views: 38

Answers (1)

trincot
trincot

Reputation: 349946

I guess heapq.heappush will create a new array

No, it performs an append to the given list. See the source code of CPython on github:

def heappush(heap, item):
    """Push item onto heap, maintaining the heap invariant."""
    heap.append(item)
    _siftdown(heap, 0, len(heap)-1)

That append is followed by a _siftdown call, which will check (and potentially update) that list to make sure it maintains the heap invariant. That process has a worst case complexity of O(log𝑛).

Here is the code for _siftdown:

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

Note how the >> operator halves the index in each iteration, so that if break never gets executed (which is the worst case), there are O(log𝑛) iterations of this loop.

The referenced file has extended comment blocks which explain the principle of a binary heap and how it is implemented. See also Wikipedia - Binary heap - insert.

Unrelated, but the comment in your code that claims that heapify is a O(𝑛log𝑛) operation, is wrong. It is O(𝑛). See How can building a heap be O(n) time complexity?.

Upvotes: 3

Related Questions