Build Heap – Intro to Algorithms

Given what we have build up so far, we can actually use the pieces to build a heap from scratch. We have the heap structure. In this case, with seven nodes and we filled them in with this random two digit numbers and it’s not heap at the moment, but we can make the heap property be satisfied and this the way we’re going to do it. We’re going to start of at the root, which is node zero and we’re going to say, okay, well, to make this into a heap, well first magically make this into a heap and make this into a heap and once we’re done then we could do down heapify on this value and everything will be fine. Alright. How do we build a heap out of this smaller piece? Well, we can do it again recursively. We can say to build a heap, rooted at this node, make this new heap, make this new heap and then down heapify. Well, how do we do this guys? Well the single two nodes are already heaps. Any leaf, anything that is a leaf already were done. That’s our termination condition. This is a heap. We’ll check them off as we go. This is a heap. This is a heap. This is a heap. Alright so, now to make this whole thing a heap, we need to do our little swap thing. So 88 gets swap, this is down heapify 88 gets swap with 30 because 30 is the smaller of the children and now that down heapify is completed this whole thing is a heap. We need to do this subtree, again same trick. This guys are already heaps. To make this into a heap, we have to swap it with the smaller of the children 13. Now down heapify finish so this is a heap and now we’ve just got the last little step to make the whole structure here into a heap, we need to do down heapify on the root node. Which means swapping it with the smallest of the children that’s the 13 and continuing recursively because that’s what down heapify does, swapping it with the smallest until we reach the bottom and that’s done. The whole thing is a heap. We made a heap. Woohoo! Perhaps even cooler. The running time is quite nice. The time it takes to build a heap out of an elements. Well, we build two heaps of size n/2 then there’s a log in step to down heapify and this is a slightly hard piece to analyze. It’s not so hard to figure out that we’re essentially running down heapify which is a log in operation on each of the node sort as a root. We know that it’s actually big O (n log n) and there’s a tighter analysis, which I’m not going to give that actually shows that this T(n) is Θ(n). We could actually establish the heap property through out the tree on n nodes in the near time, that’s pretty cool.

9 thoughts to “Build Heap – Intro to Algorithms”

1. Yeshashree Prasanna says:

Thank you! This quick tutorial really helped me as im cramming for my exams right now!

2. Roger Geng says:

your hand is so distracting, it would be better if it wasnt there

3. Elephiant says:

This is the kind of tutorials I always search for D;. quick and clear. nice one :).

4. deleteaman says:

I need to make things like this

5. Ilhan Kalkan says:

i was confused with the recursiveness but your video made it clear again. Thanks!

6. alkismer says:

Great video, very explanatory. For anyone wondering how the complexity equation came to be O(n) go to Wikipedia and search for Master Theorem.

7. Lokopi says:

Can you please give the detail of time complexity – θ(n)

8. Abner Campos says:

Thank you I was having a bad time with this topic but now I understand what's going on thanks to your explanation.

9. 黃德安 says:

great tutorial!!