2.6.3 Heap - Heap Sort - Heapify - Priority Queues

the topic for this video is heap under this topic we are going to learn about these things I will be explaining these things that is a representation of binary trees complete binary tree heap how to insert and delete in heap then heap sort this is one of the important topic and heapify this is one of the famous algorithm or a procedure for creating a heap I'll discuss this one then heaps are famous for being used as a priority queue so we learn about priority queues so these are the subtopics under this heap topic right and if you know all these things then you can understand heap sort you can also understand he be fine and periodic you unless you know these things so directly jumping on this it's difficult to understand that so that is the reason I am covering all these things so if you already know few things you can skip and go to that topic right any particular topic now before I start I have to say something see I have two courses in udemy one is for c++ second one is for data structures both the courses are for beginner level as well as advanced level means if you already know data structure and c++ you have lot of things to learn there and also if you are a beginner if you have never done any programming then you can take up c++ course and start learning programming and both the courses are suitable for academics as well as for interviews so C++ programming one courses there and that is from beginners to advanced level you can learn up to the level of it will be you can crack any interview then data structure course using C and C++ and some algorithms are it's not completely algorithm is just a data structure using C and C++ right and few algorithms are there so that subject is for academics as well as for cracking job interviews or coding interviews right so I have covered all the topics in greater detail so that will definitely improve your skills so you can buy those two courses those are paid courses those are not free and though please don't ask for free coupons the link for those courses is given in the description you can check the description and there is a discount code is there discount coupon code is that is around 10 $11 so you can click and go to udemy and if more discounts are applicable udemy will give you that discount that don't worry about that if still it can be reduced it will not use it so I suggest you take this course and by clicking on this link you go there so let us start with the topic first I will discuss about representation of a binary tree using array so here I have some examples this is a binary tree I have taken alphabets here so that easy to read this is a binary tree and if I have to store it in an array this is an array already have taken in the C C++ programming array starts from index 0 but here I have to confirm on onwards so this is just a theoretical on paper when you want to program write a program then you tend to start from index 0 also but usually this is studied by taking index 1 onwards so I have taken index 1 then these elements are stored here so how they are stored C for storing a binary tree we have to take care of two things one is we have to store all the elements second is the relationship between them who is a parent who is a child who is left child who is right child so these are the things that we have to take care so elements and the relationship between the elements so how they are preserved watch here see the elements are stored here ABCD efg so actually they are filled level by level ABCD efg yes they are filled level by level then where is the relationship the relationship between them is formed by these formulas so what are these let us look at see if any node is at index I then its left child is at index 2 into I right child is 2 I plus 1 and its parent will be I by 2 floor value so let us look into this example and observe really these formulas are used here or not let us check B B is at index 2 whose a left child of B D so where it should be to entwine so 2 into 2 4 yes it is not for then is right child where it should be 2 into I plus 1 2 into 2 plus 1 that is 5 so check on 5 yes then see see is at index 3 then it's left child s so 2 3 6 so it should be 6 years then the G is the right child it should be 2 into I plus 1 2 into 3 plus 1 7 yes it is at 7 so yes these are followed now one more thing s who's a parent of sense this is 6 6 by 2 is a 3 go to 3 yes C is the parent so you check here in the tree then 4 7 this one G who is a parent C 7 7 by 2 7 by 2 is 3.5 but we have to take floor of elements just 3 so go to next 3 yes C is there so this gives the parent so normal on that actually these elements are stored by following the formula now every time you do can't use the formula and put them right so instead of using the formula one thing we do is we fill them level by level a-b-c-d-e-f-g so that's it so this formulas are automatically followed now let us look at another example here I don't have these nodes ok no problem fill their level of 11 in b c d e 3 ends here so ABCDE so if you apply those formulas you check by yourself they are followed right left child right child and parent formulas are followed automatically now let us look at this one a B C then D no when I am filling level by level without using the formula and I want the formulas to be followed automatically then I should fill level by level and if any element is missing I should leave a gap there yes this is the important point now actually we should have its left child which is not there right child which is not there so put a blank there yes a B C Blanc Blanc de BC Blanc Blanc de this is how they're filled now if you see Dean who is a parent of a d6 by tube this one six by two three yes three who is there at the three C is there if I don't write D there if I write here then it becomes a left child of B that will be wrong so it means left child is not there for B so this place must be blank and it should be filled here so without following formulas if you want to fill them then make sure that if there are missing notes you leave a blank there so that's all about a representation of binary tree that is done using these formulas these formulas are for maintaining relationship and the elements are as it is stored in an array now next we will understand what is complete binary tree now let us learn what is full binary tree and what is complete binary tree so first full binary see this binary tree this we have already seen it so this is a full binary tree what does it mean by full C the height of a binary tree this is 0 1 2 so the height is 2 0 1 2 height of a binary tree is true and in that height it is having maximum number of nodes if you want to add any no water then the height will increase and if you remove any node then this is missing it's not having all possible node one more node is possible so you can take this you know this is having full in height 2 now this is in high 2 3 this is full binary there is no space for any new node so that tree is called as a full binary tree and if the height of a binary tree is H then a full mana tree can have 2 power H plus 1 minus 1 number of nodes maximum these many nodes so a binary tree with the maximum number of nurses a full binary know what is complete by a tree let us learn this now see look at this fun when I have represented this in an array then from last first element to the last element there is no missing element so this is complete if you look at this if you check the first and the last element there is no missing element it's a complete binary tree here from the first element of the last element if you check in an array there are some missing elements so even if there is a single missing element it is not a complete binary tree this is not a complete binary right so the definition is my definition is if you represent a binary tree in an array then they should not be any empty locations or gaps in between the elements bins from first element to last element in between anywhere right after the last element spaces there then there is no problem like suppose this array is having only five element if I have one more six location that's not a problem right but in between the elements that's the important thing now if you look at this now you tell me whether it is complete or not yes it is full as well as complete so every full binary tree is also complete monetary now check this is it complete or not check a level by level one node is there two nodes are there 1 2 3 4 nodes are there then this next next next yes it is complete binary if I remove this node then it's not a complete binary tree this is missing this is missing so no node must be missing if I remove this then this is not a complete binary tree so this is missing so if you go level by level there should not be any missing one then in this level two nodes in this level four nodes yes all are there last level all nodes are not there all those are not there no problem if all nodes are there then it's a full binary right so one more definition of complete binary this mostly you find in the textbooks see of complete money trees a full binary tree up to height H minus 1 if you hide this NC it's a full binary and in the last level the elements are filled from left to right this is one of the definition you will find in the textbooks a complete binary of height H height H already our full binary up to height H - one last level the elements are filled from left to right that same thing I am saying that if you represent this in an array you'll not get gaps like this if you're getting gaps it's not a complete binary without gaps it's a complete binary now one more important thing see the definition of complete monetary what I gave you sometimes or some authors some people call this as almost complete binary also okay but in most of the text books you will find this as complete monetary so I am calling it as complete battery now I will draw a few trees and show you which one is complete which one is not complete so that you get comfortable with complete binary trees so I'll remove this and I will show few binaries look at this is it a complete binary tree check level by level first level one node then two nodes then four nodes all four are not there if you start from left side then one two no load is missing so it's a complete Banerjee get this one row this one in the next level two nodes next level four are there all four are not there but left-hand side by exchange left side is there so yes it's a complete monetary rotus one then to this level two then next level all those are not there but first which node must be there actually it should have this node than this node then this is allowed so these two are missing so it's not a complete binary now this one first level one the next few notes okay next level all those are not there but first of all we should have this node then this node then this node then we can have this so we should have the notes from left to right but the three nodes are missing there it's not a complete binary tree so if you represent this in an array let us say this is 1 2 3 and this is 4 then 1 2 3 gap gap and the gap and then 4 so you'll get 2 3 blank spaces in between the elements so it's not a complete bantering what about this let us check first level 1 next level 2 nodes next level 4 moves must be there one two three food these are missing so it's not a complete vanity what about this this is their right two modes then four must be there one two this is missing it's not a complete one tree this one one then here two moons then here one two three four knows okay then last level all those are not there but we have this exchange left yes this is the end point after this nodes are not dead that is not a problem this is a complete bunny now you are comfortable with what is complete binary and one last point of a complete binary is that the height of a complete binary will be minimum only that is log n height of a complete binary will always be log and because unnecessary we are not going to the next level unless one of the level is filled unless this is filled will not go to the next level see unless this is filled will not go to this level it is not a complete binary if you are going to the next level so always the height of a complete binary tree will be minimum that is log and this is the interesting fact of a complete binary now next we will learn about he let us learn heap see for that I have example binary trees here this binary tree is a full as well as it's a complete binary tree yes the important thing is complete binary this is also complete this also complete now first of all heap is a complete binary tree then next condition see the condition let us look at the elements 50 then 30 and 20 are smaller than 50 years 15 and 10 are smaller than 30 and heater and 16 are smaller than 20 so it means every parent is having the value greater than all its descendants every node is having the value greater than all it is descendants so a road will have the largest value that is maximum value so yes if the elements are arranged like this then it is called as max heap so I repeat max heap is a complete monetary satisfying the condition that every in know what is having the and greater than all its descendants greater they're not equal to all so all it is descendant so duplicates are allowed here so if you have the blinkers you can have them in descendants coming into this one here this is 10 30 and 20 others children that are greater on this 35 and 40 or greater than 30 and also 10 so 32 and 25 are greater than 20 and also in turn they are greater than 10 also so here the smallest element is there in the root so every node is having the element smaller than all its descendants or smaller than or equal to all its descendants so this is called as mini heap so again I repeat mini heap is a complete binary satisfying the condition that every node is having the elements smaller than or equal to all its descendants so there are two types of heap max heap and min heap so whatever we have to study will study upon one heap and same thing applies on the next shape also so we will take max heap and study this one so we will learn how to insert and delete the element so first let us look at insert operation in a max heap I'll show you insert operation in the max heap let us understand how insertion is a ton so already I have a max heap here this is a diagrammatic representation of a heap that is complete by a tree and that is this is the array representation of same thing this is stored in an array if you check root 50 then this is 30 20 30 20 15 10 860 15 10 8 16 there are no gaps in between the elements in between these two there are no gaps so it's a complete - it's perfect let us insert I want to insert a element 16 so let us insert 16 so I want to insert the 16 this max heap so let us see see where the 60 should come a room should have the largest element so 60 should come in the root yes now what usually people think I will talk about that then I will show you what is the right method people think that 60 should be inserted here then where 50 should go 50 should go 30 that is 20 so this is small enough if they should go this side okay then where this 20 should go Bailey should come at this side so in this way it will extend in this direction 16 will come here and this will become 20 and this will become 50 and this will become 60 now if we do it like this is it a complete binary no all these are missing element then we have the 16 here this is wrong so don't insert it in the root so I have shown you the wrong procedure or wrong assumption what people will have this is wrong it is not inserted in the road then how it is inserted where it is inserted look at this the correct procedure see we actually implement in an array so that 60 should be inserted here at the last free space in an array our heap was ending here right it was ending here now I have 16 included there at this free space right so in diagram where it will be 60 will be on the left child or for 15 check it where is 15 and 4 2 4 8 yes it is a left child of 15 so this 60 is inserted here inserted here yes it's not a part of heap I have kept it separately now is it forming a heap known that condition is violated every node should have the value greater than all its descendant but you see 60 is there that is a child of 15 wrong then what to do are just the element are just the element make it as a heap or inserted in the heap how compared with the parent who is a parent 60 is greater than 15 so 16 should go up again compared with the parent 60 is greater than 30 also so it should go up and 16 is greater than 50 also so it should go up so check here in this Dyke in this array representation 8 8 by 2 4 so check with this one 4x2 to check with this 1 2 by 2 1 check with this one so 60 is compared with this one and its parent on each parent so 60 is compared with all this ancestors and it will reach its right place so it will swap all these element and 60 will there so I will draw it here c60 will come here I will draw a tree first - then I will fill the elements right after inserting how it looks like now this is our array so here I kept them empty just watch it 60 will go up 15 will come down and again 60 will go up and 30 will come down 30 will come here then 60 will go up and 50 will come down so we adjust the element like this so 60 comes here so it has moved up in the hierarchy towards the ancestors and it has reached the road because no it is the largest element so in an array if you see 60 was here so 15 when 60 was here so this 15 went there and 60 came here then again 30 went there and 60 came here than 50 went to its place and 60s in Surrey here so this is how the heap looks like diagrammatically and also in an array so this is insertion we have inserted only one element in a heap that we have taken max-heap now a little bit analysis how much time it has taken it has taken the time equal to the number of swaps so maximum how many swaps 1 2 3 so actually this is depends on the height of a tree so what is the height of a complete binary tree height of a complete binary tree is log n yes so it means the time is big-oh of log n or order of log n so the time taken for insertion is log in how many swaps are required 1 2 3 so that depends on the height log in number of swaps are required and one more thing if suppose this was not 60 if this was 6 then we don't have to swap anything zero swaps so we can say that the time taken for inserting one element in a heap is minimum Big O of 1 and maximum is log n it can be from one constant to logon minimum Tammis knows who are being is required maximum the swapping requires depends on the height so that is log n so this was inserting just one element in existing now before going to delete I have something to show you observe one thing see when we are inserting we have to send the element upwards first we add the new element as a leaf then we adjust it by comparing with the ancestors so element moves from leaf towards route so the direction of adjustment is upwards this is the important thing this is the important thing so anyway next I will take the same example then in this one only I will show you how to delete so let us look at the now let us look at delete operation on max-heap here is a max-heap with seven elements that are also they didn't have array now which element you want to delete see the first important thing you cannot delete any other element you should not delete any other element but root element so only one element is deleted from the heap without asking or without giving any options or choices only root element is related yes if you are deleting root element then only it is a heap see this heap is just like if you have seen in the market at the Fruit Shop if apples are arranged how they arrange they arranged like a pyramid heap like so the apples are arranged one above another like forming a pyramid like shape so on the top which Apple is kept the best Apple the most shiny one among all fresh one is kept on the top so that is the best one so same concept is used in heap also so all these elements are there which the topmost element best element what is best for us maximum element so that is max heap so 50 is on the top so if you want to remove the Apple which happily will remove you cannot remove any other Apple from that heap you have to remove the top most happen only that's what so you follow the same method here we will remove only the root element right similarly in the mini heap also if you say no maximum element is not important for us minimum is important then that you follow mean heap okay coming to this let us delete the element so only I can delete fifth t-50 is gone no again sometimes people mistake here the thing that thirty should go up because this is bigger okay thirty will go up then who will come into place of thirty fifteen so is fifteen goes here thirty goes here then this node is gone if this node is gone is it looking like a complete battery no so if you try to adjust as you like it will not be a complete binary tree so you have to be careful for preserving complete monetary property then what to do so when 50 is gone who should take its place see the last element in complete binary this element this element will come in its place that is 16 will come here so 16 is removed from here so 16 is brought here 16 is removed from here this is gone so 16 is brought there 50 is go gone outside we have deleted that 50 50 has gone out we have deleted it then in its place the last element in complete binary last element and complete abandoned humans in an array the last element will take its place now this is how it looks like so I will remove this one now okay I will remove this this is gone so you have already seen it it's here now now this is complete binary tree but not a max-heap so we have towards just the elements okay we will let just the element that's not a big deal ix aning complete binary property is very important so we preserve that now adjusting the element so we will adjust how from the route towards leaf we will send it so let us check how to do this compare children of this 16 that is new route which the child is greater 30 is greater so 30 will take its place 16 will come into its place so I will draw it here so here 30 goes here 20 and 8 remains 16 comes here and 15 and 10 as it is so I will fill them in this array also 30 is here 10 and 20 and this is 15 and 10 and 8 this place is free last place is free so how we have done it is see the 16 was a compared with its a children who are children of 16 2 and 3 left children right chain left children right share 1 into 2 1 into 2 plus 1 so 2 into 1 & 2 into one plus one so if you remember this formula - why do i plus 1 so this is 2 and this is 3 2 & 3 these are 3 20 and 30 are the children we compared and 30 is brought here 60 so now this is one step we have completed still we have to check with the descendents so let us check with the descendents 16 who are the children of 16 15 and 10 compare them which is greater 15 now is this 15 greater than 16 no first of all compare the children and we shave our child is greater that you compare with the parent okay afterwards you compare it but 16 is greater than both of them so leave it it's already there in max here so this is a max if you don't have to swap them so this is a delete procedure so I'll just repeat this steps quickly see always in delete we remove root and the last element in complete binary will take the place and we push the element downwards towards leaf and adjust the elements to form a max heap so we have adjusted downwards right so from route towards leaf if you remember in insert the adjustment was done from leaf towards root but now that this man is done from route towards leaf so in division adjustment is done but the direction is different so in both insert and delete adjustment is done but the directions are different now little bit of analysis how much time it has taken for deleting one element it depends on the height so what is the magazine you adjust when you have to do that depends on the height so the maximum time is login login yes so deletion takes log n time now one important thing we understood here is that from the match see for whenever you delete you get the largest element from the heap 50 was largest 50 was gone but now who is largest next largest element is 30 if you delete which will be deleted 30 then from the remaining 20 who will come and sit in the root 20 will come and sit in the room so if you delete next 20 will be deleted yes so from maxi whenever you delete you get the next largest element from min-hee whenever you delete you get the next minimum element so you get the smallest then next small as the next small it's and so on now last important thing this is very important listen carefully right see this is important here the array size was seven one element is deleted know what is the heap size six heap is still six only from one to six seventh place in an array is a free that is not a part of habeus leave it no problem our heap is still six only that space is vacant after that so it's not a problem for us but what element we deleted 50 where it is we are using it but if you want to maintain that copy of 50 there is a free space here you keep 50 here this is interesting I get 50 there is it a part of you know it's outside him yes so it's not a part of him just a space was free so I kept it there that's all away from him right now from the six elements if I delete again what will be lit it 30 will be deleted and eight will come here then we are just so 20 comes here and eight goes here then eight with it's a child that is 10 so 10 comes here it goes there so now the heap reduces to this so the heap size is 5 which element I deleted just no 30 these two places are free all the way I kept 250 there not 30 keep it here next free place if I do this what happens what happens next element will be 20 next element will be 10 and so on see this was 16 anything is so it will be so on so what happens you we are getting the elements largest the next largest the next largest in the slashes largest so if you read the elements from this side they are sorted they are sorted yes this is the idea of heaps heart if you have a heap that delete the element and fill it in the empty place obtained after deletion so if you go on filling the elements there then automatically gets sorted so from the heap go on deleting the elements and start filling them in free spaces so this is he sought so let us take fewer elements and see the complete heap sort right now heapsort heapsort have two steps first us for a given set of elements create a heap by inserting all the elements one by one then once the heap is formed delete all the elements from the heap one by one the elements will get sorted so I repeat the procedure of heaps would have two steps for a given set of number first of all create a heap then delete all the elements from the first of step create a heap second step delete all the elements from a heap so I already have some set of elements here in an array these are the elements we have to sort them so I will first show you how to create a heap how the heap will be created inside the array I am also going to show you diagrammatically so let us start suppose these are the set of elements that we have to sort they are not sorted so first of all create a heap so for that initial array these elements are initial array so we assume that in this first element is already in a heap so this is ten so right now there is only one element in the heap so when you have only one element you can call it as maxi also mean heap also it's a heap definitely it's a heap now we will insert second element so second element we will insert that is 10 is already in the heap now we'll be inserting 20 so 10 is already there so 20 we will insert so 10 here 20 here so rest of the elements I am NOT writing them okay I will be right one I will be writing one by one now inserting 20 how do we insert already have shown you compared with the ancestor that is parent and its parent and so on and try to add the element check 20 with 10 right so this is greater so 20 should go up and 10 should come down 20 should go up and 10 should come down so here in an array 2 is the in the of twenty two by two is one compared with the parent one so yes twenty will come here ten will go there right now this is him so we have a heap of two elements there's a heap of two elements now third element we will include so right now we have twenty and ten now the new element is the next three space so next three spaces this one yes so the new element is fifteen so we are going to insert fifteen now this one earlier we have inserted the elements from here right now 15 we are inserting so right now we have 20 and 10 here so 15 is in inserted here now try to adjust it how compared with the parent so who is the parent of 15 3 by 2 s 1 so temporary with the parent 15 is smaller so already it is in the maxi form we don't have to adjust so till here we got a heap now insert the next element 30 so already we have elements 2010 15 now this is the next free space right 2010 15 next free space we have 30 so 30 we are going to insert 30 this is complete by a tree but not some max-heap are just the element company with the parent and its parent so that is greater than 10 and also greater than 20 so 10 will come into place of 30 yes here it is compared with this one then again it is compared with 20 so Teddy comes here and at this place 30 will be inserted so this will modify 10 comes here 20 here and this becomes 30 now this is a heap but till here so we have four elements in heat now the last element 40 I am going to insert so right now we have 30 20 15 and 10 so 30 20 15 and 10 so the new element that we are inserting is 40 here so 40 is inserted at next free space here so it's a complete monetary but not a maxi compare with the parent yes what is greater than its parent what is greater than that also so 40 will move up so this is the parent 5 by 2 is 2 then its parent so yes 20 will go at this place and 30 will go at this place and what he comes here so it means so it means 20 comes here 30 comes here and 40 is here so this is a max-heap so one by one we have inserted all the elements and every element was inserted at a next free space and it was moved upwards and we got a max-heap now before going to the next step let us analyze how much time it has taken we have inserted and the elements total and elements we have inserted how much time it takes for inserting an element in a heap depends on the height what is height of a complete mana tree or a heap it is login so n elements each element we assume that it is moved up to the root so it is login so the time taken is and the log n so this was the heap creation for system now from that heap I will be going on deleting the elements so this place I will show you how the elements are deleted and they are also sorted so let us delete the elements now second step for heapsort already we have created a heap now the same heap I have taken this is the heap that we go now let us delete the element so we know very well how to delete the element so in this let us delete so which element get deleted 40 gets deleted 40 is gone out that who will take its place last 20 this will take its place 20 will take its place so in the diagram I will show 40 is removed and 20 will go in its place 20 will go in its place so it means this element is gone this element is gone now this is completed by entry but not a max-heap so we have to adjusts we have to adjust downwards so this 20 is gone right 20 is removed now 30 and 15 30 is greater so 30 will go in the place of 20 and 20 will come here so this becomes 20 and this becomes 30 then I get it compared to India with the 10 so it's perfect so these are the changes so now 40 is deleted and we got one free space now here I will show a large elements see we have 30 here and 20 here 15 and 10 so the elements in the heap are 30 20 15 and 10 heap is tell 4 elements only 40 which was deleted I will put it here at a free space that is not a part of heat now delete next element so next element which element will have deleted 30 will be deleted 30 is gone who will take its place last element in cupola 2010 so in this array 30 is gone so the 10 last element will come here this element came here so this is not there so one more element reduced we have to adjust this one compared with the children 20 is greater so 20 moves up and 10 comes down right so this becomes 20 and this becomes 10 so this is deleted I remove this arrow now 30 is deleted and this is in a max-heap perform now next step here I will show we have the elements 20 10 and 15 and heap is ending here 40 was already there we got one more free space so keep 30 there the newly deleted element and in the diagram this is 20 10 and 15 still we have to delete three more elements no next delete one more element which element get deleted 20 is deleted from the array this is gone who will take its place last element in complete binary will take its place 15 so 15 will come here last element in the array that is in the heap 15 comes here so this is place is free so this is gone I just already 15 is greatest so child is smaller no need to swap the element it's already perfect so this is the result then next is space I will write out this is 15 and this is 10 so this is 15 and 10 and heap is reduced still here see there were three element now there are only two early already I have 40 at the last and 30 at the second last place one more free space I got there I can insert 20 so just a store two nd I should not say insert just I have stored 20 they are kept at 20 there now these elements are deleted from the hem these are remaining still in the heap not delete next element which element is deleted 15 is deleted who will take its place last elements so it means this is gone so here also 15 is gone 10 will take its place now do you have to adjust you don't have to adjust anything now what will be the result this is 10 so this is 10 now heap ends here now we already have 20 30 and 40 here we got 1 3 space so they use 2 or 15 so that's how the elements are sorted so the heap sort first step if the elements are given then create a heap then second step go on deleting the element and store the element at the free space we are obtaining after deleting the element so finally the elements are sorted so you look at this so you have to observe it because too much board work gives there a lot of board work is there so you may miss at some place so I suggest you just pause the video and have a look at it complete example is there on board right and do it by yourself once you do it by yourself then you can remember it always how it is working just take a snapshot or copy everything from my board if we do the analysis already creation process we have seen and log in creating heap and login now how much time this is deleting of all any an element is taking and there remains we are deleting and each element takes how much time for deletion also it takes login time we have already seen it so that is n log n so n log n for creation and log n for deletion so total how much 2 n log N and this is Big O of n log n right 2 times of log n is also dependent on n log n so the time is order of n log N or Big O of n log n so heap sort takes n log n time so that's it this is heapsort now I have to its new heapify and heapify is a process of creating a heap already we have created a heap how it is different it's different how does different we will see but before that if you remember here we were inserting the element always in the leaf and we were adjusting towards route adjusting towards who it was sent from leaf towards route adjustment was upward now in heapify the direction is different how it is done I will show you how to remove the sensual now he makes topic is heapify heapify is a procedure for creating a heap so already we saw how to create a heap by inserting elements one by one here also will do the same thing but the procedure was inserting an element in the leaf and adjusting upwards now let us see how he b5 works so for explaining heapify already I have an array right and if you see it diagrammatically is this a binary tree and so complete binary tree but it's not a max-heap we want max-heap now if we just repeat the procedure of creation let us look at it quickly already we saw in creation process what we did we kept tonalities inserted 20 20 went up then inserted 15 then inserted 12 than 40 then 35 then 18 one by one we inserted starting from this element so we inserted except this element we inserted 2015 12 or t25 18 so we started from left to right is it possible if we change the direction can we create a heap let us start from right to left so if we start from right to left then shall we still that just the element upward no let us do it downward downward how in the deletion if you remember we were adjusting the element by sending it down towards leaf from root so the direction was from top towards leaf that procedure will follow let us follow the process now I am explaining heapify watch this first go to element 18 look down there are no children so only a single element look at all of the nodes just 18 and it's descendants there was no descendant so 18 is a hint yes then go to next element 25 25 look downwards it's a heap there is nothing there are no children it's alone it's a heap 40 is a heap next element 40 next element 12 downwards it's a he no you will understand what does it mean what I was saying just next next element 15 so from here at just 15 downwards yes children are there compare which is greater 25 so 25 will go up and 15 will come down yes this is the procedure 25 will go up and 15 will come down so 25 will go up and 15 will come in its place this one right so if you look only these nodes 25 15 and 18 it's a heap yes only one element I have adjusted now next after 25 this one 20 is there this is over right 15 was there this is over now we are on second element right this one look downwards is it a max-heap no it just this one so compared with the children 40 is greater so 20 will come here 40 will go up right so 40 this will be changed to 20 and this will become 40 so I have just adjusted just two elements now after second element first element here only this element is not in the heap so adjust it compare with the children 40 is greater so 40 goes up 10 comes here compared with the children and 20 is greater so 20 goes up 10 comes here right so this will be swapped with the child so this will become 40 and this is 10 then again swap with the children that is 20 and 10 2012 and 20 was there so it will be so after 20 and this comes here this is a heap so we adjusted the elements at downwards and we started from the last element so we have scanned this array from right to left the procedure we were using in the deletion after deletion we were at in Delhi when same procedure we followed and we got the he created so this procedure is called as heapify right direction is different that's all right and what is the time taken by this one analytically the time taken by this hippie fie procedure is Big O of n we go theta Omega or whatever you want notation you use anything commonly we use Big O so this is Big O of n so if you remember the procedure for creating a heap creating a heap so creating a heap was and the login we go off and log n right but this is heapify heapify procedure is order of n so this is faster now what is the minimum time taken for creating a heap Big O of n using HIPPA file so that's all about HIPAA Phi now the last thing is what are priority queues it's a simple topic so I will finish with that one next we will see priority queues now priority queue priority queue so actually cuman's FIFO but priority cuman's it's not free for strictly the elements will have priority and they are inserted and deleted based on the priority right so always if in a queue when you want to delete always we want highest priority element from the queue the element having the highest priority that should be deleted for so this is the discipline of priority queue elements are inserted with the priority when you delete we want higher priority element so let us see what does it mean by high after ID see these are the numbers what is the priority of a number number itself is the priority okay here in our example number itself is the priority there are other example of priority queues also like in operating system also there is a concept of priority queue it is not same as that one this priority queue is mostly used in algorithms right so let us see what is the priority eight is the variety of eight six is the priority of six so 10 is the priority of 10 so that number itself is the priority then who is higher priority I can say that smaller number higher priority so which is high as turning this one then this one right then this one yes smaller the number higher the priority so three is of highest priority here so if I delete I want three from the array then otherwise even I can say that larger the number higher priority I can say this also so larger number higher priority so who is having higher priority 10 then 9 then 8 so yes when I want delete I should get 10 from that one so this is about priority queue elements they value itself is priority and there are two methods of giving priority smaller number higher priority or larger number higher priority okay now let us see how to insert and delete see in an array if I want to insert suppose I have one more element simply I can insert after this one now say when I want to delete from the this type of priority queue I want 3 then for how much time it takes for deleting an element from an array or orphan because if I am deleting 3 I should shift the rest of the elements rest of the elements I should shift say takes order of n time so if you implement periodic you just using normal array than the time for insert or delete may be order of M so I don't want to discuss in detail you can study it by yourself means you can analyze by yourself if you say no I want to keep them sorted order then for sorting also it takes time again for a deletion or insertion you have to spend order of n time then what is the better method heap which takes how much time login time for insertion and login time for deletion so yes heap is a best data structure for implementing priority queue so if you have smaller number higher priority then create a min heap if you have larger number higher priority then use max heap same set of numbers I have created already created I mean he already created maxime so for one element insertion how much time it takes login right then one element deletion how much time it takes login so this is the best data structure which works faster otherwise if you use normal array like this then insertion may take maybe deletion is faster otherwise deletion will take order of endtime and insertion may be faster any one of the operation will definitely take order of n time but in heap the time taken is login so heap is a faster data structure for implementing priority so that's all about periodic you so predict you can be implemented using heaps of either min heap or Maxie if you want always smaller number min heap if you want always larger number max so that's all in this video and if you want to take the course you can check in the description and you can buy the course for C++ and data structure subject there are two different courses right so go through the course see the contents and then you decide that's all

Channel: Abdul Bari

Views: 918,762

Rating: 4.9537148 out of 5

Keywords: Heap, Heap sort, priority queue, priority queues, heapify

Id: HqPJF2L5h9U

Length: 51min 8sec (3068 seconds)

Published: Fri Mar 08 2019