heapq module python

Question

I'm using the heapq module to determine the smallest item in a list.

I have this below code, but the heapq.heapify() return value is None.

How do I get the result in a new list?

>>> a=heapq.heapify(lista)
>>> a
>>> lista=[1,2,3,4,5]
>>> a=heapq.heapify(lista)
>>> print(a)
None

Attestation

Answer 1

heapq.heapify doesn't return anything, it heapifies the list in place; it's far more efficient to do it that way:

>>> import heapq
>>> lista = [44, 42, 3, 89, 10]
>>> heapq.heapify(lista)
>>> lista
[3, 10, 44, 89, 42]

If you need a new list, create a copy first:

>>> lista = [44, 42, 3, 89, 10]
>>> newlist = lista[:]
>>> heapq.heapify(newlist)
>>> lista
[44, 42, 3, 89, 10]
>>> newlist
[3, 10, 44, 89, 42]

That defeats the purpose somewhat, of course, as copying the list has a (linear) cost too.

If all you need is the smallest item in a list, the min() function will be just as fast when locating just the one smallest element (both heapify() and min() scan the input list once, so O(n) cost):

>>> min(lista)
3

If you need more than one smallest value, by all means use a heapq, especially if you add items later on. If you cannot alter the original list, need several smallest items, see looking for an inverted heap in python for an efficient nsmallest implementation that creates a new heap from an input heap with only a fixed number of smallest values.

Companion

he may not be familiar with typical heap implementation and traversal – Sackville

Answer 2

You have to use heapq.nsmallest(k,arr) function. //k here is 1 as you want one minimum value.

>>> a=heapq.heapify(lista)
>>> a
>>> lista=[1,2,3,4,5]
>>> a=heapq.nsmallest(1,lista)
>>> print(a)
1

Rennold