7.9 Heap Sort | Heapify Method | Build Max Heap Algorithm | Sorting Algorithms
ฝัง
- เผยแพร่เมื่อ 25 ส.ค. 2024
- CORRECTION: at 42:50 heapify call for delete logic would be maxheapify(A, i-1,1) and in maxheapify method instead of while loop we can write if statement. :)
Discussed Heap sort and Heapify method to Create a Max Heap form Array. Step by step instructions showing how to run Heap Sort with its pseudocode.
DSA Full Course: https: • Data Structures and Al...
******************************************
See Complete Playlists:
C Programming Course: • Programming in C
C++ Programming: • C++ Complete Course
Python Full Course: • Python - Basic to Advance
Printing Pattern in C: • Printing Pattern Progr...
DAA Course: • Design and Analysis of...
Placement Series: • Placements Series
Dynamic Programming: • Dynamic Programming
Operating Systems: // • Operating Systems
DBMS: • DBMS (Database Managem...
********************************************
Connect & Contact Me:
Facebook: / jennys-lectures-csit-n...
Quora: www.quora.com/...
Instagram: / jayantikhatrilamba
#heap #datastructures #jennyslectures
CORRECTION: at 42:50 heapify call for delete logic would be maxheapify(A, i-1,1) and in maxheapify method instead of while loop we can write if statement. :)
Thanks!
👍
👍
After correction also sorted output in not coming !
-----------------------------------------------------
#include
void printArray(int *A, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", A[i]);
}
printf("
");
}
void swap(int *A, int i, int j)
{
int temp;
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
void maxHeapify(int *A, int n, int i)
{
int largest = i;
int l = (2 * i);
int r = (2 * i) + 1;
if (l A[largest])
{
largest = l;
}
if (l A[largest])
{
largest = r;
}
if (largest != i)
{
swap(A, largest, i);
maxHeapify(A, n, largest);
}
}
void heapSort(int *A, int n)
{
{
int temp;
for (int i = n / 2; i >= 1; i--) // build max heap
{
maxHeapify(A, n, i);
}
for (int i = n; i >= 1; i--) // deleting
{
swap(A, 1, i);
maxHeapify(A, i - 1, 1);
}
}
}
int main(void)
{
int A[] = {4, 6, 1, 2, 45, 12, 40};
int n = 7;
printArray(A, n);
heapSort(A, n);
printArray(A, n);
return 0;
}
I came here to tell this. I have been trying to solve this problem for 3 hours.
Anyway, thank you.
The beauty of these lectures is that even faculty learns from here to teach their students....you are amazing mam....
acha
So basically we're all going to university to get our degree but we learn all the stuff from youtube tutorials.
yep and always from a smart person from india, but at least this woman is beautiful!
Yeah welcome to understanding India's Education System
true, university is just an outline :D
@@tungtruong5904 true said bro college sirf namki he lekin sab log asli padhai youtube parshe hi karte
ive watched so many indian youtube tutorials , ima get hindi degree till end of college
I’ve subscribed and turned on notifications and you didn’t even have to ask for it. That’s the mark of a quality uploader. Thank you for sharing your valuable knowledge.
Agreed
Spam
First I watched your CountingSort video...then didn’t stop watching your other videos. Thats the quality of your videos. This generation students are very lucky to have open university and talented lecturer like you in youtube. In reality all the students wont get best teacher in their classrooms. Kudos to your work, keep doing 🙏, I read so many program sites couldn’t explain clearly like you explain the example with all the iteration passes. Doing 1 or 2 iteration passes will not give deep understanding of the solution. 🙌🏻
No other person can explain these algorithms better than Jenny Mam. Everything is explained beautifully with pictorial representation as well as with code. Thanks a lot Mam!
Thanks mam. Passed my 3 semesters by watching your videos. 🙏♥️
Also I for the life of me could not understand why to take n/2 as the starting point, while looking at a piece of code for Heap sort. You explained that critical bit of info with a use case. Thank you!
Thank you, I really appreciate the fact that you are taking the time to do these videos, which is really good quality, top information regarding algorithms. You are an amazing teacher, I am sure you put in loads of hard work to come up with a method and solution which is easy to understand.
I sometimes feel very happy that I m preparing for GATE2020😍😍really very clear explanation thankyou!
Did you cracked it?
Yeah....same question....did you cracked it??
Jenny your lectures are such great help! I’m relieved to have found your channel! Thank you for being so thorough with your explanations :)
My university lecturer play your video in class and teach us algorithms 😂❤
🤣
@@sushmapandey7145 😂
O bhai...
@@sushmapandey7145 😂😂😂
Waste of money in your University
Actually i want to give as many as likes possible for your lecture but here he gave only one.....😍😍
Most valuable gem of IT and data Science : Jenny Ma'am 😊
You are only in TH-cam who explained this algorithm in structured and easy way.👍
Excellent video. The concept of heap sort and heapify is easy to understand but the code can be a little complex to come up with. I tried for 3 hours and watched numerous videos and stumbled upon this gem. You earned a follower! Thank you so much!
mam u taught like god...
each concept is now embedded in me.
Thanks for clearing my doubts
...ur teaching stye is unique
Thanks a lot for this lacture. Your videos help me alot for my exams and you explain in a very good manner thanks once again.☺😊
Explantation is excellent and simplified way.
At (42 min)in delete method looping should start with (i=n-1) if its start with n it will give one garbage value in array
Thank u mam for that grt video.
Aap hi ho meri real DSA waali mam.
My dsa marks credit goes to you only.
Love you mam
My college faculty copying your lectures mam😂
Same 🤣
Same😂
C benaya tumko
beauty with brain --- deadly combination
A very intuitive lecture by you ma'am. All of my doubts are cleared after watching this. Very Very thank you ma'am.
27:26 will start from here for revision
You really are one of the best teachers for data structures and algorithms.
@Jenny's lectures CS/IT NET&JRF A small correction, in the logic of sorting loop, instead of maxHeap(A, i-1, 1) we have to use maxHeap(A, i-1, 0) because the index starts from 0 and our first element will always be at index 0.
Here index 0 contains sentinel value bro so we start from index 1 only
i am leaning itpec and when i see your videos of all , more easy to learn and have a graet solutions for exam . i really really appreciate .
Mam you r 100000 times better than my college mam..your presentation techniques is very pleasant..thank you mam to teach us in this way.❤
Great lecture. Concept Explained in simplest terms. Thank you, Jenny
What a great explanation Jenny! Was thinking to skip heap sort thinking its 46 min explanation but actually worth it! Now I know heap sort from leaf to root xD
Leaf to root XDDD
Was preparing for the internship drive(interview season), wanted a heap & heapsort revision and here it is. Saved once again :)
So how was your interview...??😬
@@vishaldas5692 lol😂 I got internship 🙌😇
@@himanshuyadav7327 Haha great u got on this covid situation....!!🥳
There should be if clause instead of while, because we dont need loop. we are just comparing the values.
Yea
Thanks. Keep up the good work.U just saved my semesters
you are a wonderful teacher. My whole DSA basic I clear from this channel. thanks mam. and request you to bring more content related to university subjects..
😇🙂
mam ur voice is soothing to my ears, very pleasant to have u as a teacher.
My college professor and your explanation is very easy
One of the best teacher on you tube. Thanks mam for all your efforts u put for students and keep making such videos.
First for all we are converting our array into heap using heapify method.
In heapify the we are starting from none leaf node so we are eliminating leaf node therefore we have used i=n/2; and we passing parameter as I.
And in other for loop we are going to sort the heap and here we going to use deleting root node method for sorting therefore we passed 1 instead of i.
Thankyou Ma'am.
You're teaching is very nice.🥰
Wonderful teaching I am now just able to remember after listening only one time and cuteness overloaded
tremendous lecture on heap sort. Highly recomended.
In the deletion, our array size remained same as we are sending n in it!!
Isn't it wrong,
I think Maxheapify(A,i-1,1) would be there?
Correct bro.
And one more thing in place of while loops there will be simple if condition in heapify function.
Thank you so much brother......I had the same doubt ....
Yes you r correct because after swapping 1st element with n th. Element. We have to heapify only at n-1, otherwise it will again heapify whole array
@@akshatkumar2956 But bro i-- to already loop mein ho raha ha so shouldn't we write (A, i, 1) ?
@@BSEss It would be wrong as we are making the swap first and calling the Heapify. For instance, if you include the n on the first iteration of Heapify, it would be swapped with its parent (n/2).
The last dry run has cleared my doubt. Mam you are gem for us.
Being a teacher,, you are good at your job... Let us enjoy and learn well... Fantastic..
That was amazing explanation; i was so stuck in heap sort part :,) thanks
thank u miss , im computer sci student , this is very helpful
Maam, your way of teaching is awesome. Thanks a lot.
super mam you was mother of data structures
her teaching style is same as my college professor. just amazing
I think
In the deletion part the call to heapify must be like:
MaxHeapify(A,i-1,1);
As if we pass n after execution it will put 15 in last again and 30 in middle so tree would not be MaxHeap anymore.
And seperate from it
Thankyou for being such awesome teacher😇
Tyvm for explaining such a complex operations in a simple and effective way
Always end up watching your video every SINGLE time. Thank you so much for all your tutorial.
Amazing explanation mam , no one can replace mam ! Almost k watched your videos it's very useful and understandable
U re explanation is super
Mam Jinny Thank you sooo Much agaar ap na hoti tou data structure ka course parhana bhot mushkil Hota Huge respect for you mam .Luv From Pakistan
Thanks a lot Miss for all your sorting videos...these has just helped me pass data structures lab !! :)
Me: Where can I learn Heap sort?
Jenny: Here only.
आप सभी देखने वालों से निवेदन है, एक बार मेरे चैनल पर आकर ज़रूर देखें
th-cam.com/users/AtharDhamtariplaylists
@@Atharhashmisir lots of playlists...good content..wish u all the best..
Hello api,, i am from Bangladesh..
I have seen many videos about heapsort 😪😪but none of this could able to explain the algorithm as clearly+easily as you....😊😊
You lecture just amazing💚💚💚 api❤❤ and very much helpful to me. I am very grateful to you. 🥰🥰
Also expecting more lectures about data structure and algorithm from you..🥰😻😻😻💚💚
Thanks ma'am for all the videos. It helps a lot for solving all the problems in ADA nd DS.
"Prolific programmers contribute to certain disaster." author ~ "Niklaus Wirth"
that last part were you said it is heap sort....that was like magic..i was afraid of heap sort thought it was difficult but you explained it so magically
wow .. nice explanation.. i shared this video in my class group
Paying lakhs in the college and these TH-cam videos are more helpful than my entire life
we are going to college for completing 75%attendance but there nothing to learn but actually we learn from you tube❤❤
Thank you ma'am. Your videos had helped me a lot before my exam. From your videos I could understand clearly. After that I recommended your videos to some of my friends too
Video is long but worth it 👍 thanks ma'am we study a lot with yr lecs 👍
mam your video is so long .but it is really helpful.i lave learned all sorting method only region for your lecture ..* * *************************************
U r awesome mam....... tomorrow I have a sem 3 ....iam super satisfied with ur explanation mam tq......
one of the best Explanation i ever heard
😍❤
Thank U❤ Angel❤
Simplest logic explanation for complex function maxHeaify(). You are great Maam
You are amazing.I looked for such a video for heap sort which is so easily understandable.Thanks mam.
You explain like a pro 💓
Thank You Soo much for this Conceptual Video 💜
Very nice ..... Just a little error;
In heapsort function in second for loop
MaxHeapify(A,i-1,1);
i had the same doubt, *(n-1) actually........thanks
Yes , I also open the comment section with the same doubt.
Yes, you are right..
Thank you it is working now.
@@manjushreej7588
help me dude its not working
#include
using namespace std;
void swap(int *x,int *y)
{
int temp=*x;
*x=*y;
*y=temp;
}
void maxheap(int a[],int n,int i)
{
int largest=i;
int l=(2*i);
int r=(2*i)+1;
while(la[largest])
{
largest=i;
}
while(ra[largest])
{
largest=r;
}
if(largest!=i)
{
swap(&a[largest],&a[i]);
maxheap(a,n,largest);
}
}
void heap(int a[],int n,int k)
{
for(int i=n-1/2;i>=0;i--)
{
maxheap(a,n,i);
}
for(int i=n-1;i>=0;i--)
{
swap(&a[1],&a[i]);
maxheap(a,n,1);
}
for(int i=0;i
mind blowing explaination...now am big fan of you
Very good lecture this helped me alot in my exam to score better thankyou so much
I watching many videos but not understand that video very help for me
While in deletion we have to store the value in order to make it the order of ascending as in heap sort we delete only the root node so that's we take the value of i as n.
No wordss mam.....excellent
Wow , mind blowing 😊😊😊 what a explaination
Mam you are really a true teacher ❤ and your are very helpful 😊
It took me a long time to understand what she is saying ! Not because she is bad at explaining , I was just not able to hear anything once I saw her .
Btw ! Thanks for the info . Keep it up.
Mam your explanation so nice.
It's very helpful for me .
You are doing a great job.
Thanq mam 😍
Good explanation with technical approach..
Your lecture is awesome.
It's a very good explanation. Keep up the good work, madam.
39:22 is important....... Thanks for this easiest explanation........
thank you so much for your efforts ma'am!
Thq so much mam , code bhi smjh me aa gya clearly......thq so much
Mam your explanation is always so simple and easy to understand thank you for putting these video's on TH-cam :)
Today is my paper and I am so much confused about paper 🤣 firstly I think that I can,t perform good in paper . but now I am watching your videos to solve paper .so , finally I can say that I can perform best in paper🤩🥰.thanku mam💕❤️💖
Mam a lot help full you'r lectures me and myfriends .upcoming generation teachers be like you teaching.so much better. I never forget you mam because.Internet using any work is done .this is possible. I proudly say.
students can never survive without TH-cam (including me)😭
your explanations are amazing, thank you !
Didi your teaching procedure by English communication is A1 .. lv from west bengal didi ❤
I asked sorting in an mnc interview and and I passed it with flying colours✨✨ because of your vedios mam thanks alot Jenny mam for this excellent explanation 😍😍
Wow great congratulation 🥳❣️
@@vishaldas5692 thanks bro 🤜
Ur great mam I love Ur teaching
Ma'am your teaching is just amazing and brilliant 👏
The concept and the understanding the code by you is great
Hey. I think there might be a mistake at the end. Lets say we have the Tree like you've drawn from the first half of the method. Our Array is now 30,17,20,1,5,10,15.
Now we swap the first and last Element in the Array. So now its 15,17,20,1,5,10,30. When we now call the MaxHeapify method we check whether the first Element ist still the largest in the tree.Since 15 is less than 17 and 17 is less than 20 the largest Element is now 20. We swap the 20 with 15. Now we call the MaxHeapify method again but since we give the method the Array with size n it still contains the 30 at the end. Meaning the 30 would swap with the 20. So if im correct this means we have to decrement the variable n after we use the swap method in the second half of the HeapSort method so MaxHeapify gets called with n-1 instead of the full array.
Bro it will be i only because here we are passing index and in the method definition it is consider as length if u r right kindly check for the array elements 4,5,6,7,11,67,45,67
No its i - 1 that we have to call in max heapify (deletion)
maxheapify(A, n-1, 1).
Very well explained.