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

Question

What is the method for heapify library heapq python? How could I use it in a list, for example?

Answer 1

Heap

Before you realize what the method is for heapify has to understand how a Heap. For documentation of Heapq from Python we see that the implementation uses a Heap Binary as min-heap.

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

Illustration of this principle:

The rule for a min-heap is that a parent element must be less than or equal to a child element. In a max-heap this rule is precisely the opposite.

The previous figure is only a visual representation of what a heap is, however it is arranged in an array, with a specific organization. The elements are arranged, looking at the tree, from top to bottom and from left to right.

Following this rule the heap so illustrated would look like this in an array:

But the same relation exists in this array, although implicit:

For Heaps with first index a 0 the formula to discover the children of an element is:

Filho Esquerda = 2 * i + 1
Filho Direita = 2 * i + 2

In which i is the position of the element in question.

Exemplifying for the element 17 who has the position 3:

Filho Esquerda = 2 * 3 + 1 = 7 => posição 7 que corresponde ao valor 25
Filho Direita = 2 * 3 + 2 = 8 => posição 8 que corresponde ao valor 100

Python

Let us now turn to the use of this heap python. We can start by constructing a list of the values shown in the previous figures:

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

Now as we call the method heapify this list will be transformed into a heap with all the features seen above:

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

Note that the array layout was not exactly the same as shown in the previous figures, but remains a heap valid and equivalent.

Now you can take advantage of heap that has and continues to use more library functions heapq. By way of example we can use the heappop which removes and returns the first element of heap. Being this one min-heap the element to be removed 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

It is quite possible that right now you are wondering why you use a data structure as a binary heap. Well, this data structure offers you different complexity for most operations, some of them faster than the ones on a list.

Time complexity with O notation for a Heap binary:

This can bring you advantage depending on the algorithm you have, and your goal.

Documentation for the heapify and to the heappop

References: Heap on wikipedia