CODEWITHSUNDEEP
pythonpython-2.7
satya sai
satya sai

Reputation: 46

Heap with lists in python

a=[1,10]
b=[2,20]
h=[]
heapq.heappush(h,a)
heapq.heappush(h,b)
a[0]=5
heapq.heappop(h)

pops [5,10] instead of [2,20]

If I have used heapq.heapify(h) before popping up, it gives correct answer : i.e [2,20] Is it always required to heapify the list before popping in case you have changed any of the list values?

Upvotes: 1

Views: 7196

Answers (1)

Bharel
Bharel

Reputation: 26900

When using heapq, list.sort() or any other sorting module like sortedcontainers, modifying a mutable item such as a list will cause the internal sorting to be disrupted. Usage of tuples in that case is recommended as it will prevent accidental corruption of the sort.

When using heapq or bisect, the module thinks the list is already sorted and the algorithm used works only on sorted lists. Modifying the sorted list will break the algorithm and produce unexpected results.

If you change a mutable object, you must re-sort the list if you want it to function correctly. heapq.heapify() is indeed the way to sort it if you're using heapq.

Upvotes: 3

Related Questions