What is the functionality of the "heapify" method of the heapq module?

Heap

Before you know what the heapify method is for you need to understand how a Heap works. From the Python HeapQ documentation we see that the implementation uses a Heap Binary as min-heap .

A heap of this genre is organized as a binary tree, where each element can have a left and right child, and the smallest element is at the top.

Illustration of this principle:

Theruleforamin-heapisthataparentelementmustbelessthanorequaltoachildelement.Inamax-heapthisruleispreciselytheopposite.

Thepreviousfigureisjustavisualrepresentationofwhataheapis,butitisarrangedinanarraywithaspecificorganization.Theelementsarearranged,lookingatthetree,fromtoptobottomandfromlefttoright.

Followingthisruletheheapasshownwouldlooklikethisinanarray:

Butthesamerelationexistsinthisarray,althoughimplicit:

Forheapswithfirstindexto0theformulatodiscoverthechildrenofanelementis:

FilhoEsquerda=2*i+1FilhoDireita=2*i+2

Whereiisthepositionoftheelementinquestion.

Exemplifyingforelement17thathasposition3:

FilhoEsquerda=2*3+1=7=>posição7quecorrespondeaovalor25FilhoDireita=2*3+2=8=>posição8quecorrespondeaovalor100

Python

Nowlet'susethisheapinpython.Wecanstartbyconstructingalistwiththevaluesshowninthepreviousfigures:

lista=[100,3,2,17,19,36,1,25,7]

Nowwhenwecallthemethod heapify this list will be transformed into < in> heap with all the features seen previously:

import heapq #necessário importar heapq

lista = [100,3,2,17,19,36,1,25,7]

heapq.heapify(lista)
print(lista) #[1, 3, 2, 7, 19, 36, 100, 25, 17]

See this example in Ideone

Notice that the array array was not exactly the same as the one in the previous figures, but it remains a valid heap and equivalent.

You can now take advantage of the heap that you have and continue to use more heapq library functions. For example we can use heappop which removes and returns the first element of the heap . This being a min-heap element to remove is the smallest:

menor = heapq.heappop(lista)
print(menor) #1
print(lista) #[2, 3, 17, 7, 19, 36, 100, 25]

See this example also in Ideone

Motivation

You may well wonder at this point why you should use a data structure as a binary heap. Well, this data structure gives you a lot of complexity for most operations, some of them faster than a list.

Time complexity with O notation for a Heap binary:

Thiscanbringyouadvantagedependingonthealgorithmyouhave,andyourgoal.

Documentationfor heapify and for heappop

References: Heap in wikipedia