What does heapify() function do? And what is a heap?

A heap is a data type which is guaranteed always to have its minimum (for min-heap) or maximum (for max-heap) value “at the top”, meaning that if you call **heap.pop()** you will always pop the minimum or maximum value.

Once that value is popped, or when you add a new value to the heap, you must *heapify*, which means rearrange the values in the heap so that the minimum or maximum value is again at the top.

So if I have `list = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]`

And then `heapify(list)`

What would I get?

I tried it in the text editor and got “None,” but I’ve seen an example where the list was `li = [5, 7, 9, 1, 3]`

and the output was ‘[1, 3, 9, 7, 5]’. I’m not quite sure what this means.

There is no built-in heap data structure in Python; you must program it. They are covered in the **Complex Data Structures** course of the **Computer Science Track** here in Codecademy.

A heap is a list that is conceptually structured as a binary tree (each parent has at most two children). Nodes are added from left to right, and each child node is greater than its parent. The “heapified” list [1,3,9,7,5] satisfies this structure, when read from left to right

```
1 # 1 added first
3 9 # then 3 and 9 as child nodes
7 5 # then 7 and 5 as children of 3.
```

The next two numbers added to the list would be children of 9, then the next two, children of 7. Either popping the 1 or adding any new number would require a rearrangement - heapifying - to maintain the structure.

Following this pattern, you can see that the list`, list = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]`

, that you provided is already heapified!

```
1
2 3
4 5 6 7
8 9 10
```

If the 7 and 9 were switched, would it still satisfy the heapified structure?

Yes, since all child nodes would be smaller than their parents.