I don't understand how I can properly use heapq module.
I realized that without transforming my list to a heap (without using heapify) I can still use other functions which require a heap as input (heappop, heappush..). So when do I need to use heapify?
Should I create an empty list, transform it to a heap using heapify, and then use it? I tried this. I got TypeError.
my_list = heapq.heapify([0])
heapq.heappush(my_list, -8)
TypeError: heap argument must be a list
heapq.heappush(my_list, -8)
In the example below I can push -8 to my list with heappush if I don't transform my list to a heap. However when I want to see the min element of the heap, it gives me 0. In the heapq documentation it says that I can reach the min element using the index 0.
my_list = [0]
heapq.heappush(my_list, -8)
print(my_list, my_list[0])
output: [0, -8] 0
I'm trying to use it in a loop, so I want to be able to perform quick push and pop operations without transforming a list to a heap in each iteration, it would take O(N)
You should use heapify when you don't start from an empty list and you want to transform the list to a heap inplace.
>>> queue = [1,9,2,4]
>>> heapify(queue)
>>> queue
[1, 4, 2, 9]
When you start from an empty list, then you can perform the operations such as heappush, heappop, and heappushpop directly on the list.
Example:
>>> queue = []
>>> heappush(queue, 3)
>>> heappush(queue, 1)
>>> heappush(queue, 4)
>>> heappop(queue)
1
>>> heappop(queue)
3
>>> heappop(queue)
4
You get an error, because you are using the return value of heapify, which is None since it's inplace.
>>> res = heapify([1,9,2,4])
>>> res is None
True