CODEWITHSUNDEEP
pythonheap
Alchemist
Alchemist

Reputation: 81

Why heappop time complexity is O(logn) (not O(n)) in python?

For a list, the heappop will pop out the front element. Remove an element from the front of a list has time complexity O(n). Do I miss anything?

Upvotes: 8

Views: 4633

Answers (4)

Raymond Hettinger
Raymond Hettinger

Reputation: 226714

A heappop() rearranges log(n) elements in the list so that it doesn't have to shift every element.

This is easy to see:

>>> from random import randrange
>>> from heapq import heapify, heappop
>>> h = [randrange(1000) for i in range(15)]
>>> heapify(h)
>>> h
[80, 126, 248, 336, 335, 413, 595, 405, 470, 592, 540, 566, 484, 970, 963]
>>> heappop(h)
80
>>> h
[126, 335, 248, 336, 540, 413, 595, 405, 470, 592, 963, 566, 484, 970]
>>> #       ^----^---------^----^----^----^----^---------^----^----^--- elements that didn't move

Note that the popping operation didn't move most of the elements (for example 248 is in the same position before and after the heappop).

Upvotes: 13

Josh Lee
Josh Lee

Reputation: 177875

The documentation is somewhat misleading if you're thinking about what list.pop does.

If heap is a minheap, then heap[0] is indeed the smallest item. Python's list.pop method returns the last element of the list, but heapq.heappop returns the smallest (first!) element of the heap. However, it does this by popping off the last element of the heap (which is an O(1) operation on a list), swapping it with heap[0], bubbling it up (this is O(log n)), and then returning the value removed from heap[0] to the caller.

So: list.pop returns the last item from a list and is O(1). heapq.heappop returns the first item to you, but not by shifting the entire array.

Upvotes: 6

Robin Davis
Robin Davis

Reputation: 632

Take a look at the implementation of heapq.heappop: https://svn.python.org/projects/python/trunk/Lib/heapq.py

It doesn't remove an element from the front of the list, it just returns it and replaces it with something else which takes O(logn), and reduces the length of the underlying list by removing the last element.

Upvotes: 0

llllllllll
llllllllll

Reputation: 16434

Heap pop is indeed O(logn) complexity.

What you are missing is that pop from a heap is not like "removing the first element and left shift all elements by one". There is an algorithm to move element inside the list, after popping, there is no guarantee that the remaining elements in the list are in the same order as before.

Upvotes: 1

Related Questions