Heap - Build Max Heap

In this video, I show you how the Build Max Heap algorithm works.

[@garic8423]

10 years later this is still really helpful!

[@ozzyfromspace]

Watched at x2 and it immediately brought the algorithm back. Clearly you're amazing at presenting information. Thanks, mate!

[@brecoldyls]

Great, simple, and concise explanation. Thank you

[@chrise202]

at 5:10, after i=1, your algorithm stops according to the code (for i=1 to 1). You have not explained how did you found out that the LEFT child of index i=1 does not align with the max_heap rules. You did it via visual inspection instead :(

[@williamshaoul8088]

The way we'd know if a node did not follow max_heap rules is by having the maxHeapify function being recursive. There is a conditional at the top of the algorithm that checks if A) the node we are at is a leaf or B) either child of the node has a value that is greater than the current node's value that is being passed through. If the current node is a leaf we can't heapifyDown anymore, but if either child is greater we check which one has a greater value and do a regular swap. Then we recursively call the function again. This process allows for a natural "trickle" down the heap, and for the recursion to be killed if the base case conditional is true (the current node is a leaf OR both children are less than the current value)..

[@colecook834]

Thank you

[@Fanaz10]

yea that was wack

[@gamefreak1675]

Yo! best video for explained how to structure maxheaps! Good job!

[@nurulathirah3807]

This video is such a great help..thank you so much😊

[@theone6853]

Your explanation is very easy to understand

[@varunsingh6480]

Hi the algo starts from half of the length to 1, but when we reached at index 1, we destroyed the max heap property at index 2, but algo stops at 1. In the video we revisit the 2 index but algo is already stopped at index 1. Its unclear to me

[@shreypatel9379]

Kinda late but the rearranging of index 2 is taken care of by the Max-Heapify(A,1) call which is done during the last iteration of for loop. *As you might know that Max-Heapify called at a particular node takes care of the subtree at that node i.e. the subtree at that node follows max heap property when Max-Heapify function is done executing. * So Max-Heapify(A,1) is called which swaps 5 from index 1 and places it at index 2. * Then it swaps 5 with 37 * So on and so forth This way 5 "floats" down to the place it is supposed to be. Then the max-heap property is satisfied for index at root node i.e. node index 1.

[@DannyStopMotions]

Thank you, Tony Hawk :)

[@mrchedda]

Thanks. Good video but just unclear on the last step once the root was swapped, how, programatically does it know to check the left subtree randomly? Also. What presentation software are you using? Thanks!

[@Z00CE]

Assuming we also take care of array boundaries correctly, the MaxHeapify( A, i ) algorithm goes something like this: 1. largest = indexOf( max{ A[i], A[2*i], A[2*i+1] } ) 2. if largest != i, then swap( A[i], A[largest] ) and MaxHeapify( A, largest ) Also, I used Pixelmator to draw during the video. Thanks for watching!

[@mrchedda]

+zooce thanks for the reply! Appreciate it!

[@adityaprasad1574]

Wowwwwwwwwwwwwwwww

[@nurulfadillah1248]

this is really helpful, thank you!

[@tobiasgehtumdiewelt3455]

you explain it so easy (y) thx

[@patelji...9123]

Awesome explanation..... Thx ❤️

[@maxkellerer1923]

wish that someone explained like this in the lecture

[@user-yd9xy3rb4x]

You’re out of this world

[@CantBeTamed53]

THANKS FOR TEACHING ME THIS! YOU'RE A HOMIE!

[@nandkishorenangre8244]

Thanks it really helped me bro.....

[@HostVisible]

Great video!

[@chasemedia7870]

Thank you - super clear and easy to follow. What software are you using to present your examples? I noticed you were able to erase a specific color and leave the rest of the board untouched.

[@Z00CE]

I used Pixelmator, which has layers (the effect you saw of me erasing certain colors).

[@TF2Shows]

when i = 1 why did u max heapify again? its exit loop

[@logan2116]

great explanation

[@husseinmohammed4020]

great video

[@nicklasnilsson8217]

Nice I got it. Just wonder at the last step after the pointer i is at the root, do you then just check the whole heap a for broken properties or is there a more sophisticated approach to it? Thanks

[@Z00CE]

Nicklas Nilsson, the last step (when i is at the root) is to simply call Max-Heapify, which fixes the rest of the issues in the Heap. So, to re-cap, first you fill up the heap, top to bottom, left to right (just for visuals - its actually just an array). Next you begin calling Max-Heapify from the bottom (middle of the array) to the top. Max-Heapify will correct any issues within the "sub-tree" that it is working on. As it moves upward, it continually fixes the Heap (all the way to the bottom from where it is currently being called). Hope that helps clear things up! Thanks for watching!

[@nicklasnilsson8217]

+zooce Ah okey, so everytime you call maxHeapify you have to check its child subtrees if it broke any properties and if so, swap until it is bigger than its children further down the tree?

[@rajantamang]

I too had problem understanding the last one .. thanks for the answer

[@souravkalal3831]

Same here 😀😀

[@sahidulll]

How do you go back and forth to check whether parent is greater than children? It's easy to swap with a pencil but how do you do in terms of coding? Thanks.

[@omerkatz9509]

You check that the array index i is greater than the items in index 2i and index 2i+1. So the first thing you do in terms of code is find out how long your array. You divide that number by 2 and round down (if the size was odd) and that would give you the first parent. And then as you go down from the last parent to the first parent you always check i against 2i and 2i + 1 (which are the indices of the array that represents the tree).

[@nathanemiliano6209]

you prolly dont care but if you guys are bored like me atm then you can watch pretty much all of the new movies on instaflixxer. Have been streaming with my brother these days =)

[@amoszahir7346]

@Nathan Emiliano Definitely, been watching on instaflixxer for since november myself :)

[@jubinsoni4694]

Nice Explanation Bro

[@mohammadyahya78]

Very clear explanation. Thank you very much.

[@darshitakumar7913]

Thanks! This helps :)

[@japananh1]

Thank you so much. Easy enouh for me! :)

[@MartinThePooh]

Hey i have a question on you... I understand why we needed to heapify node 2 after decrementing "i", but how do you explain it from algorithm point of view? is there something like post-for-loop check of rules or how?

[@blueknight4684]

If you had to swap, you should heapify on the index that got swapped

[@Shobu]

Thank you !!

[@claexlife]

thanks homie love you

[@nekokun4361]

Thank you :)

[@apelmahmudorkut6496]

Very helpful tut

[@prashanttgs]

*heapful ;)

[@nicopostigo123]

Thank you!

[@hiyamghannam1939]

Thank you zooce, This was fantastic, just wanna ask, I have a hmework were I must implement the class heap, should a build real nodes or all of the work is on an array ?

[@chaitanyabalanagu626]

For those wondering how this algorithm works as it stops in the middle, you need to write a condition to check if maxHeap property is applied for the whole list everytime and repeat the process of heapify if it fails, here is an example import java.util.Arrays; public class MyClass { static boolean maxHeapFormed = false; public static void main(String args[]) { int[] nums = {5,12,64,1,37,90,91,97}; while(maxHeapFormed == false){ maxHeapify(nums); checkMaxHeap(nums); } System.out.println(Arrays.toString(nums)); } public static void checkMaxHeap(int[] nums){ int leftChild; int rightChild; for(int i = nums.length/2;i>=0;i--){ leftChild = 2*i+1; rightChild = 2*i+2; if(leftChild < nums.length && nums[leftChild] > nums[i]) return; else if(rightChild < nums.length && nums[rightChild] > nums[i]) return; } maxHeapFormed = true; } public static void maxHeapify(int[] nums){ int length = nums.length; for(int i = nums.length/2;i>=0;i--){ heapify(nums,i); } } public static void heapify(int[] nums, int i){ int maxValue = i; int leftChild = 2*i+1; int rightChild = 2*i+2; if(leftChild < nums.length && nums[leftChild] > nums[maxValue]) maxValue = leftChild; if(rightChild < nums.length && nums[rightChild] > nums[maxValue]) maxValue = rightChild; if(maxValue != i) swap(nums,maxValue,i); } public static void swap(int[] nums,int highest, int i){ int temp = nums[highest]; nums[highest] = nums[i]; nums[i] = temp; } }

[@hamzajammy]

good job

[@hamzajammy]

thank God

[@combofriend4461]

Can someone explain to me how this is different than what's being described in the first video? The first video is explaining max reality but it's also describing calling it from the last node with a child back to the root to build a heap just like this one is right? Am I missing something? The steps being walked through on both are the same aren't they?

[@wangbiqing2888]

Visually I see the last swap between 5 and 37. but programmatically how to detect the disorder after looping all node index?

[@rohitchauhan5587]

Nice explanation .. Love from India sir

[@liveyourlife3659]

what happens if we have 9 elements instead of 8. 9 divided by 2 ? 4 or 5...does that technique applies in that situation?

[@Z00CE]

We `floor` the division in the equation, so if there were 9 elements, then that part of the algorithm would evaluate to 4 because the `floor` of 9 / 2 is 4. Then at index 4, we call MaxHeapify, to `heapify` the subtree at with node 4 as the root. I hope this answers your question. Thanks for watching!

[@Vlad-rk5go]

3:45 why do we swap 97 and 1 instead of 97 and 12? Even overall I can't see any benefits over using a binary tree.

[@derdev6574]

thanks

[@muhammadzeeshan0013]

good i got the key now ;)

[@ankeshpandey3630]

Nice video sir but i have a doubt. What did you draw at the start of the video. I mean was it a min heap aur something else. In our college we are first asked to draw heap and then sort it into max or min. So what did you draw at first, please answer Thank you :)

[@chloetang211]

its good explain!

[@richardatkins3623]

In all these videos no one explains how to actually enter the numbers from the array into the tree in that format (left to right)

[@Z00CE]

The tree is only visual; there's no actual tree data structure. The way in which you access the array is representative of a tree (e.g. left = 2i, right = 2i + 1).

[@raist1er]

The floor of 7 and 6 divided by 2 give 3 twice, did you skip to 2 on purpose?

[@mjjply]

it doesnt matter, because it will only switch based on value.

[@ERol-du3rd]

Does this run in O(n) time?

[@kalvikaraiyila9693]

what can we do if given elements in an array are same for e.g. A ={2,2,2,2,2,2,2,2,2,2}

[@Z00CE]

Basically, this algorithm would simply iterate through the indexes ( i ) and the calls to Max-Heapify( A, i ), wouldn't have any work to do. Here's a quick run-through of the Max-Heapify algorithm: kzbin.info/www/bejne/a5qlhoeDjKynf7M. Thanks for watching, BTW!

[@kalvikaraiyila9693]

zooce ..., ya but if a ques arises that the given array A={2,2,...,2} belongs to max heap or min heap what would be the ans...,

[@Z00CE]

That question, as you've stated it, would be ridiculous (it's a trick question, really), and doesn't test one's knowledge of min/max heaps. The answer is, both.

[@kalvikaraiyila9693]

ok tq fr ur response...,

[@swastikagarwal8605]

what is max heapify exactly... what does it do...

[@abdulwahab182]

Which gadgets you are using for screen recording

[@gpugpugpu]

Couldn't you have chosen a better example where the recursion of the downHeap algorithm comes in earlier? You don't even mention it until the end of the video and you kind of make it seem like it's a special case, even though the recursion is happening every time (only it is being exited earlier). It's kind of a fundamental function for heaps.

[@Herotruth]

I dont see the difference between MaxHeap(a) and MaxHeapify(a, i).... It seems the only reason we have MaxHeap is so we can pass one perimeter.

[@Z00CE]

This is only one implementation of this, which is a static implementation. This means that the algorithm MaxHeapify, doesn't know anything about the array, so you have to give it an array and the index of the subtree you want it to heapify. There are obviously other ways to do this.

[@payalsagar1808]

thankyou! INDIA..

[@pawelloozik]

I have i =3 whats that mean ?

[@colestecyk9957]

rip my ears

[@Lordycal]

ngl this made no sense. How did you have that graph already made? shouldnt you be making it as you go?

[@masterjif9506]

Well it doesn’t matter now cause you passed your exam anyway

[@LLee0]

I find that it is easier to implement by constructing a new array, instead of modifying an existing one: medium.com/@randerson112358/lets-build-a-max-heap-161d676394e See the section: # Williams Algorithm: top down while not end of array, if heap is empty, place item at root; else, place item at bottom of heap; while (child > parent) swap(parent, child); go to next array element; end Finish the program in one hour.

[@prasanjeetdas3555]

that's a wrong way.

[@abhishekgautam1063]

Wrong Process of Max Heapify, you are not doing recursion!

[@UrkoCornejo]

Thank you best heapify explanation i saw !!🦾