HeapSort | Heapify method to build a MaxHeap in O(n) | DSA-One Course #32

Hey guys, In this video, We're going to learn about HeapSort. HeapSort is a sorting technique that uses Heap to sort Arrays. We'll also see how the heapify method works. And how to use this method to build a Heap.
More info on the Time complexity of building a heap: www.geeksforge...
🥳 Join our Telegram Community:
Telegram channel: telegram.me/re...
Telegram group: telegram.me/ds...
🚀 Follow me on:
Instagram: / anuj.kumar.sharma
Linkedin: / sharma-kumar-anuj
Twitter: / realanujbhaiya
💸 Use coupon code ANUJBHAIYA on GeeksforGeeks to avail discounts on courses!
📚 Complete DSA Playlist: • DSA-One Course - The C...
Complete Android Development Playlist: • Android Development Tu...
Hashtags:
#anujbhaiya #dsaone
Ignore these tags:
heapsort
heapsort algorithm
heapsort example
implement heapsort
heapsort ita
python heapsort
heapsort italiano
algorithm heapsort
heapsort using maxheap
heapsort example step by step
algoritmo di ordinamento heapsort
heapsort example in data structure
heap sort
sort heap
heap sorting
heapsorting
heap sort ita
heap sort in c
heaps
método heap sort
heap sort in java
heap sort example
heap sort in hindi
heap sort program
heap sort analysis
heapify
max heapify
heapify algorithm
min heapify
heapify method
heapify code
max heapify code
max heapify algorithm
bottom up heapify
min heapify array
what is heapify?
heapify pseudo code
build heap vs heapify
build heap and heapify
شرح heapify
hepify method
process of heapify
max heapify example
min heapify function
max heapify function
maxheap using heapify
min heapify and max heapify
max heapify time complexity
difference between heapi
heapsort
sorting algorithms explained
merge sort explained easy
explained
create heap sort
heap sort
heap sort with example
heap sort analysis
heap sort code
implement heap sort
exercise on heap sort
what is heap sort
build heap in linear time
heap sorting algorithms
heap sort implementation
heap sort algorithm
heap sort in data structure
heaps in golang
merge sort explanation with example
heap sorting in data structure
heaps in go
create heap
heapsort
heap sort explained
heap sort explained with example
heap sort algorithm explained
heapsort example step by step
heap sort code explained
heap sort explained in python
heapsort algorithm
heap sort code explained in python
heapsort example
heapify algorithm explained
heapsort example in data structure
analysis of heapsort
heap sort explanation
heap sort example
create heap sort
heap sorting example
heap sorting
heapsorting
heap sort analysis
heapsort
heapsort algorithm
heapsort c++ code
code
heapsort example
c code
heapsort java
heapsort in c++
implement heapsort
heapsort explained
inside code heap
code for maxheapify()
heapsort sorting algorithm
dsa heapsort practical in c++
heapsort example step by step
heapsort example in data structure
how to code
c game code
inside code
sample c code
c program code
c code example
c code library
heap sort
heap sort c++
sort heap
heapify
max heapify
heapify code
heapify algorithm
min heapify
max heapify code
heapify method
max heapify algorithm
heapify pseudo code
what is heapify?
heap code
max heapify example
what is complexity of heapify routine?
شرح heapify
hepify method
code
build heap vs heapify
build heap and heapify
explained
analysis of max heapify
heapify complexity
code for maxheapify()
complexity of heapify
heapify in heap
bubble sort explained

[@chirag7694]

I wasn't able to understand this topic from anywhere except this video, Thanks a lot Anuj Bhaiya 😊

[@shubhamsirothiya2551]

Helpful.

[@angadkochhar9885]

the for loop can be started from 1 till n/2 right?there wont be any problem or change?

[@arijitbarua9908]

We anybody completes this entire course with full focus and is able to solve other questions using these concepts then he/she can easily crack any company's top package job. Anuj Bhaiya is doing this job for free. Idk how to thank You. If I get placed in a good company with a good package the entire credit goes to you not my college faculty. Lots of Love ❤❤❤

[@rishabsharma5307]

Make more videos on questions patterns

[@i_mchick5311]

best explanation on utube. U r the true king of DSA . Your style of teaching is the best ,far better than animated contents. TRUE KING ANUJ BHAIYA.

[@harshitpanjwani2460]

dsa ke questions karaye bina dsa course bana dala..kya dsa ke liye bas concept zaroori hai ya concept building bhi ?

[@AryanSingh-zv5ch]

Khud bhi kuch krlo ki sab yahi krae

[@cosmosXverse]

At 19:55 u said heapify run O( logN )...but last vd u said it's O(n).please someone clear me

[@sarthaksharma9656]

@@harshitpanjwani2460 spoon feeding is not good bud

[@moviesasylum8531]

@@cosmosXverse i thinks its like heapify does take O(n), but extracting/deleting an element it takes O(logn), and we are doing it for n times so, O(nlogn). Now, O(n) + (nlogn) = O(nlogn) (approx)

[@Kumarvivek-uv5hf]

Yes . Very much clear now. Great explanation !! keep the good work going .

[@nabamitabose9310]

Yes it was helpful . Thank you so much 🥺❤

[@AshishKumar-pq6pr]

Awesome lecture....more different types of questions please..... frequency increase please...... love your lectures

[@rohandevaki4349]

you said heapify is O(n) ,now you are saying heapify is log(n) at 20:03

[@manmeetsingh1537]

Y Muje bhi doubt h

[@LimaCharliee]

@@manmeetsingh1537 building a heap is O(N) but heapify is O(logN)

[@saketgautam4417]

Bhaiya please make video on how to ask for referrals.. I mean format or something. How to build connections..

[@zubairmujeeb8455]

Sir, Left and right should be calculated with the help of 2*i+1 for left and for right 2*i+2. correct me if i am wrong?

[@AyushGupta-zn8jl]

Yes, in zero based indexing.

[@BusinessIdeas-]

and in that case int i of for loop will start from i=(n/2)-1 till i>=0

[@code_with_me2070]

@@AbhishekKumar-zl1ho yeah both are same , heapify is just a algorithm to create heap in less time because insertion take O(nlongn) time and heapify take O(n) time

[@Fenil3357]

Best explanation of heapsort❤️🔥

[@devanshgupta5555]

sir bhut din se heap me problem a rhi thi apki video ne sab clear kar diya thank you so much sir #DSAONE

[@rajeshagarwal4137]

thanks a lot.far better than any animated content

[@anshulgoel1940]

if we replace 10 with 15, at the last step, the array is not a max heap. Basically when you replace an element from top to a child, we will have to check for all the child nodes of that changed node.

[@sankalparora9374]

Nice and clean refresher. No Bs. Thanks

[@pruthveshshetkar1263]

Thank you Anuj bhaiya , very helpful and up to the mark content 🔥

[@cosmosXverse]

At 19:55 u said heapify run O( logN )...but last vd u said it's O(n).please someone clear me

[@starkendeavours7072]

At #13:43, won't it be Heapify(arr, n, largest - 1)?? Because the heapify will start from n/2'th position, as the code says here at #14:16, yes we can start heapification from any random location as he said, but acc to this code, it should be largest - 1!!

[@anantmishra2382]

Totally agree

[@sirajuddin4852]

we just swapped i with largest , now the tree at largest index may not follow the heap property , as it replaced by less element. So he called heapify on largest.

[@AyushSingh-xo4ed]

yes very very helpful sirrrrrrr

[@jaypatel9392]

Thank u so much Anuj Bhai. Today is my exam n I am not getting heap concept properly but now everything is clear ❤️❤️❤️❤️❤️❤️

[@user-hq8pt4lv7w]

Sir, how to start preparation for software companies ....currently in 1st year bsc computer science Is there any hope for getting a good job in software companies just after passing bsc comp sc as a fresher?

[@user-hq8pt4lv7w]

Please reply, Sir

[@aayushgupta2998]

After bsc if possible go for mca then it will be easy for you to crack big software companies.

[@deepakjonnalagadda2141]

best explanation for this concept. I had lot of struggle trying to understand from other videos.

[@satakshipal5008]

yes it was helpful bhaiya

[@vimalkumardubey6834]

Thanks bhaiya for these lectures 🤍🌝🌝

[@dhirajjadhao6392]

are iska hi to wait kr raha tha mai

[@SwagGM]

In the heapify function there is no neccessity call it again if we are traversing backwards, it makes the complexity worse... and it wont be O(n). HOwever if traversing from forwards it's required...

[@MUHAMMADALISHAFIQUE-w2d]

anuj bhai you are a great lecturer seriously amazing teaching style ♥

[@izzu-u9e]

Can u tell me max heap sorting is ascending or descending?

[@ajith4249]

One word about this video -->Too many small mistakes which makes difficult to understand and incomplete information

[@jyotipandey3156]

Loads of ❤️....it was really vryyy beneficial..please keeep going 👍👍

[@niladridutta5737]

very useful vedio for students

[@popeyetech9634]

Bhaiya hm log in concept ko asani se seekh jate hi but bhaiya in concepts ko hmesha kaise yaad rakhe please make a video on this topic also how to memorize your concepts for forever 🙏 Tell us the best way to do this.

[@divyanshverma4148]

Practise bro... Questions related to it. Not 100 q. Just 4 to 5 different type Questions. Its just like maths, the more question you solve the more you understand

[@vaibhavchaubey8373]

Best explanation of heapsort❤🔥

[@anshulgoel1940]

Why we have to compare with sibling. The existing sibling is already smaller than parent. This is ensured at every element insertion.

[@prasunkamilya6111]

please start the array index from 0, for the best code understanding and systematic.

[@akashprajapati1450]

Bhai apne confuse kardiya.... First leaf node n/2 se start hoga... Apko array 0 index se Lena chahiye tha... Mai previous vedio me confuse hogya tha jab apne left & right child find krne ke bare me bataya

[@yshanroy2264]

Bhaiya plzz come on unacademy CP plus platform...

[@deepanshumahour3318]

YES, IT WAS HELPFUL

[@grx4.067]

Anuj bhaiya + code with Harry = placement pkaa

[@azgharkhan4498]

I wish if you could explain how is it O (n). thats more important i feel

[@akr1831]

Thankyou bhaiya for this amazing video

[@sonudhariwal6207]

YES, IT WAS HELPFUL

[@agyaani8060]

Where m I getting wrong getting wrong output! class Solution { //Heapify function to maintain heap property. void heapify(int a[], int n, int i) { // Your code here // Your code here int largest = i; int l = 2*i; int r = 2*i + 1; if(la[largest]) largest = l; if(ra[largest]) largest = r; if(largest!=i){ swap(a,i,largest); heapify(a, n, largest); } } //Function to build a Heap from array. void buildHeap(int a[], int n) { // Your code here for(int i = n/2; i>0; i--){ heapify(a,n,i); } } void swap(int[]a,int i,int j){ int temp = a[i]; a[i] = a[j]; a[j] = temp; } //Function to sort an array using Heap Sort. public void heapSort(int a[], int n) { //code here buildHeap(a,n); for(int i=n;i>1;i--){ swap(a,1,i); heapify(a,i-1,1); } } }

[@animeshpandey2911]

Self notes: heapify fn expect krta h ki usse niche ke el already heap ho.....tbhi agr kisi index pe heapify fn call kiya jaega ...to vo khud ko ur apne niche vale ko heap me badal dega........... isiliye build heap bnate time hm last ke nodes se heapfiy fn call krna start krte hai

[@roopeshverma9719]

Yes, it was helpful, made so easy to understand!!

[@jackwalker2947]

Best explanation 😅

[@kumarayush998]

This video cleared my doubts on this topic.

[@gauravjindal007]

great explanation

[@sarthakjoshi21]

bhaiya can u give me code of this i don't lnow where i am doing mistake so if it possible so provide a raw code

[@sarthakjoshi21]

pls help bhaiya

[@ashokdurunde1814]

Best explanation of heapsort❤🔥

[@samadahmed7487]

at 1:56 sir why do we have to compare 50 with its parent's child and then the parent, because we are inserting an element in a heap so if the element which we are inserting is greater than its parents then it must be greater than the other child of that parent and if it is not then also we don't compare as max Heap property will be followed by the tree .

[@atulkhajuria4315]

Yes u r right

[@aakanshasoy3921]

Sir values to put krke explain kar skte h kya heapsort wale function me value compiler kese put kra wo clear ni hora

[@roy_kousik]

I was waiting for this video thanks bhaiya

[@kingshorts12590]

Thank you sir appreciate your hard work

[@ap360]

Best explanation on KZbin

[@jayisampelliwar5246]

Sir array start from zero index and why we take 1st element as 1 index? I guess we are skipping 0th index or what?

[@allwindsouza9595]

Yes we skip the 0th index ... Broke my head on the same confusion too 😂

[@jayisampelliwar5246]

😅😅

[@lovedeepsingh1793]

If you want to start from 0 index then use left=2*i+1 and right=2*i+2.It will work if you use starting index as 0.

[@ABCD-gn5uw]

@@allwindsouza9595 it is so because lets say we put 1st element at 0 and its children being 1 and 2 if we want to go back to 0 we will divide 1 and 2 by 2 which gives 0 and 1 respectively. Now see that both children are pointing to diffrent parent.

[@beingIndian1234]

bhai aapki video ki playback speed km kar k dkhna parta hai.. kitna fast bolte ho aap :)

[@vishalmishra1937]

@anuj bhaiya why in for loop it is from n/2

[@amarjeetkumar-hk2jl]

nlogn is better than n , then why we are sorting in O(n) ?

[@Manojkumar15629]

Love you from Aligarh ❣️

[@kngofdrkness6587]

Gfg wale question me answer wrong a rha hai

[@kaustubhgaikwad2562]

Return block if its recursive?

[@amansinghrajput9681]

Hi bhaiya

[@ankushmane1333]

Wow badhiya

[@baluchavan3047]

Saho padaya bhai😙🔥

[@so0709]

In your max_heapify function you need to compare the left child with the 'largest' as well as with the right child before initializing the 'largest' variable with left and the same goes for right child.......otherwise if both the left child and the right child are greater than the parent node and the left child is the largest, then as per your function it would still consider right to be the 'largest' and the structure will get affected. .......................................................@ANUJ Bhaiya

[@Ctrl-Alt-Hack]

While running the Heapify Code, I'm getting ArrayIndexOutOfBound error Any idea what could be wrong ???

[@user-jt9er4gb3m]

yes, it's very very helpful. and i think this is the best explanation on KZbin

[@sahanabalghare8833]

very good and on point explaination

[@noadsensehere9195]

little more clarification is needed

[@namanverma4818]

if we had already checked that our largest is not updated then we should break there. We didn't need to check for largest!=i. WILL IT BE MORE EFFICIENT?

[@furqanahmad5446]

very helpfull.. thanks

[@piyushagarwal8458]

Guru Ji, Pranam !!

[@ganeshvhatkar7166]

Most understandable video on KZbin for Heapsort, Heapify, Build Heap with pseudo code

[@jibeshkumarpanda6151]

As youtubers do, Hide ambiguous moments by explaining the easiest example.. If you want to let students understand clearly, introduce handling the ambiguities, with tougher examples

[@kommurusreenath5400]

Yes It was very helpful......awesome lecture.Thanks for creating this content

[@sangramsingha11]

A nearly complete binary tree with level order traversal of 10 20 30 15 10 in this case the leaf node are 30 15 and 10. For floor(N/2) + 1 will give leaf node start at value 15. please correct me if i am missing something over here.

[@Shivamashish5236]

Hello Anuj sir I m Ashish from Allahabad Sir is request for you U saw your front end and back end video Can you please make video on how Amazon, Google,fb that build back end and database plz .. try it 👍🏻

[@ChandanKSwain]

Seriously ,i am very thankful to you,for this level of explaining. Still making some confusion bcz of array's indexing from 0.

[@MuhammadZeeshan-fn3vk]

It was really helpful ❤

[@cat-codes1on1]

"Yes , it was helpful"

[@sug_madic7683]

But we don't compare to its sibling of same parent brother while inserting

[@codewithaakash6826]

yes , it was helpful

[@MridulGuptaBEE]

Yes, it was helpful.

[@architsangal]

Yes, it was helpful.

[@mdnadeem6343]

yes it was helpful bhaiya

[@jatingoyal9575]

#Bhai full stack web developer or software's engineer ma kiya difference hota ha pls rpely me

[@New_Movie_Watch]

superb video bhaiya

[@cloudverse260]

Very helpful lecture

[@saurabhchangulpai5997]

Yes ,It was helpful

[@amalkrishnas1696]

Very helpful video

[@riyaanhussain7851]

Code is saying array index out of bounds. Someone please help

[@shyamkumar2606]

Bhaiyas DSA course is best but is there any course for DSA in cheap and best

[@GunjanChoukade]

Thanks a lot bhaiya☺

[@sahllsaharn4664]

ir i implemented heapify using iteration while loop and started form last element and i checked the parent then i checked the child to fulfil the heap property ... thanks sir

[@anchaljaiswal6861]

First bhaiya

[@aashutoshgandhi371]

thanks , i needed that.

[@Shivam-bz8qy]

Yes it was helpful