Question About heapq

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

1 Like

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.

1 Like

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
1 Like

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.

1 Like