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