I think there's benefit to both, these tutorials are vital, but then you should start doing heap problems on LC after you know how a heap works for example, I just got to the heap section on LC 75, but I forgot the heap operations so came back to this as a refresher, then will now do the LC 75 problems
Assuming we have an array of N integers, heapify goes through half of elements and checks whether a value X at index K is greater than the values at indices 2K and 2K+1. This starts at index N/2 because the latter half is already a heap of 1 element. This iterates starting at N/2 and works its way to index 0. Thus, each check is O(1) × N/2 times, which is O(N) time. If we had a tree object to represent the heap, heapify does a postorder traversal where it calls heapify on its children before heapifying itself compared to its children. In this, we do 2 comparisons per call after recursing, and we do N/2 recurses. This gets us to check N/2×2 recursive checks which is O(N) time. The reason heapify is not O(NlogN) is because we do not call push every time. We simply do in-place heapify foe maximum efficiency.
@@Bluedragon2513 so for each iteration starting at N/2 going to 0, the current element X is compared to only one other element? I didn't know this was the case. And yes, in place heapify would make sense to not call push every time. Could you please reply with some structured English on the main concepts of how heapify works? Id appreciate it
@@Krokodil986 So, for each iteration starting at index N/2 going to 0 which we will call i the current index with its element e = array[i], we will compare e with elements e1 and e2, which lie at indices i*2 and i*2+1. We are doing N/2 iterations. Each iteration, we are checking 2 things: e vs. e1, and e vs e2. In total, we will be doing O(2) checks per iteration * O(N/2) iterations: we arrive at O(N) iteration checks for heapify. ~~ No, we are not doing only 1 comparison, we will be doing 2 comparisons. However, O(2) == O(1) because big-Oh decides the polynomial degree. If this didn't make sense, I will try with better English
@@Bluedragon2513 thank you, I understand what you said By "structured English" I meant pseudocode which is vague and non-technical. In other words: what are the main basic steps that heapify executes? After you compare e to e1 and e2, what do you do after this?
@@Krokodil986 (assuming we are doing a max-heap) After comparing e with e1 and e with e2, you will select the greatest value. If e is greater than e1 and e2, then do nothing. If e is greater than e1 and less than e2, then swap e and e2 If e is less than e1 and greater than e2, then swap e and e1 If e is less than e1 and e2, then swap e with the higher of the two. Technically, I was wrong when I said you only do 2 comparisons as you'll technically be doing 4-5 comparisons given some nested code. Here's some pseudocode for the whole heapify process: for i from N/2 to 0: e = arr[i] e1 = arr[2*i] e2 = arr[2*i+1] if e > e1 and e > e2: continue else if e > e1 and e < e2: swap(arr,i, 2*i+1) else if e < e1 and e > e2: swap(arr,i,2*i) else if e < e1 and e < e2: if e1 > e2: swap(arr,i,2*i) else: swap(arr,i,2*i+1) end for The reason why we cannot just compare e with e1, swap if needed, then compare e with e2 is because it is not necessarily the case that e1 when transferred over to e2's spot. However, it is guaranteed to be the max when transferring e1 or e2 to e1's spot.
Yeah, this is very true. I was kind of annoyed at my phrasing during editing this. I meant sort in a loose term that it organized them to follow the heap structure, but I agree it was confusing and made it sound like it can actually sort properly
@@ramalshebl60The rules to how those trees are build. Don't quote me on those time complexities tho. The binary tree doesn't really have a rule except that each parent has a max of 2 children. No sorting whatsoever, not recommended if you want to sort or search for values later on, as it's not better than the list it started with. Adding, deleting and searching in O(n). Generally just not worth it. A search tree is a binary tree with the added rule that each element of the left subtree of a node is smaller/eq than the root and right subtree larger. Unbalanced: adding, deleting and searching in O(n). Balanced: everything in O(log n) A heap only says that all elements of the next level must be smaller (max heap) or bigger (min heap) and that a heap musst be complete aka. The tree is filled to the max, except the last "row" (standard binary heap, there are others). Time complexities as shown in the video. Sorting in O(n log n).
it does...it might look like nlogn but the leaf nodes are not being compared which are half and if you calculate like that you can prove that not every node needs log n comparisons thus n
Master Data Structures & Algorithms For FREE at AlgoMap.io!
I like these tutorials better than the leetcode problems. We learn more by these explanations. Subscribed! 🎉🎉
Glad to hear it :)
I think there's benefit to both, these tutorials are vital, but then you should start doing heap problems on LC after you know how a heap works
for example, I just got to the heap section on LC 75, but I forgot the heap operations so came back to this as a refresher, then will now do the LC 75 problems
Thank you for posting these informative shorts
You're very welcome!
I like your voice man, it has some mini explosions from time to time.. And they sound so satisfying
Lolol lol thank you I think 😂
@@GregHoggthose are called voice cracks
You’re an inspiration. Please continue doing these videos
Thank you greatly, and of course I will :)
Give this man a medal for O(n) sorting 😂, wonder how many people fail interviews for these things
The fact that heapify is done in O(n) does not imply you can sort an array in O(n).
@@nobrainnogain7255Idk what function are you talking precisely, I'm talking about him telling heapify gives you the sorted array in O(n)
????????? what is your point exactly, heapify is a bigO(n) operation for bottom-up and log n for top-down.
They're saying he incorrectly said that heapify sorts the array
@Anthony-oz1jc yes, heapify is O(n), but in the video, he said heapify sorts the array. It does not.
So to sort it's
O(n) - heapify- * o(logn) - heapify down or up- => o(nlogn)
Which the same time as sort function in python 😊
Thank you for your video
My pleasure!
U the man
Can you make a follow-up on how to use python's heapq module for min/max heaps? Love these!
Was actually considering doing that, thank you for the suggestion :)
You da man@@GregHogg
This was good
Wait why is heapify O of n when it calls the push method n times? I would have thought it would be O of nlogn
Assuming we have an array of N integers, heapify goes through half of elements and checks whether a value X at index K is greater than the values at indices 2K and 2K+1. This starts at index N/2 because the latter half is already a heap of 1 element. This iterates starting at N/2 and works its way to index 0. Thus, each check is O(1) × N/2 times, which is O(N) time.
If we had a tree object to represent the heap, heapify does a postorder traversal where it calls heapify on its children before heapifying itself compared to its children. In this, we do 2 comparisons per call after recursing, and we do N/2 recurses. This gets us to check N/2×2 recursive checks which is O(N) time.
The reason heapify is not O(NlogN) is because we do not call push every time. We simply do in-place heapify foe maximum efficiency.
@@Bluedragon2513 so for each iteration starting at N/2 going to 0, the current element X is compared to only one other element?
I didn't know this was the case. And yes, in place heapify would make sense to not call push every time.
Could you please reply with some structured English on the main concepts of how heapify works? Id appreciate it
@@Krokodil986
So, for each iteration starting at index N/2 going to 0 which we will call i the current index with its element e = array[i], we will compare e with elements e1 and e2, which lie at indices i*2 and i*2+1.
We are doing N/2 iterations. Each iteration, we are checking 2 things: e vs. e1, and e vs e2. In total, we will be doing O(2) checks per iteration * O(N/2) iterations: we arrive at O(N) iteration checks for heapify.
~~
No, we are not doing only 1 comparison, we will be doing 2 comparisons. However, O(2) == O(1) because big-Oh decides the polynomial degree.
If this didn't make sense, I will try with better English
@@Bluedragon2513 thank you, I understand what you said
By "structured English" I meant pseudocode which is vague and non-technical.
In other words: what are the main basic steps that heapify executes? After you compare e to e1 and e2, what do you do after this?
@@Krokodil986 (assuming we are doing a max-heap) After comparing e with e1 and e with e2, you will select the greatest value.
If e is greater than e1 and e2, then do nothing.
If e is greater than e1 and less than e2, then swap e and e2
If e is less than e1 and greater than e2, then swap e and e1
If e is less than e1 and e2, then swap e with the higher of the two.
Technically, I was wrong when I said you only do 2 comparisons as you'll technically be doing 4-5 comparisons given some nested code.
Here's some pseudocode for the whole heapify process:
for i from N/2 to 0:
e = arr[i]
e1 = arr[2*i]
e2 = arr[2*i+1]
if e > e1 and e > e2: continue
else if e > e1 and e < e2: swap(arr,i, 2*i+1)
else if e < e1 and e > e2: swap(arr,i,2*i)
else if e < e1 and e < e2:
if e1 > e2: swap(arr,i,2*i)
else: swap(arr,i,2*i+1)
end for
The reason why we cannot just compare e with e1, swap if needed, then compare e with e2 is because it is not necessarily the case that e1 when transferred over to e2's spot. However, it is guaranteed to be the max when transferring e1 or e2 to e1's spot.
Please make videos on heapss
Heapify doesn't sort the array
Yeah, this is very true. I was kind of annoyed at my phrasing during editing this. I meant sort in a loose term that it organized them to follow the heap structure, but I agree it was confusing and made it sound like it can actually sort properly
How is it any different from a normal tree which is sorted
👍
"Everything you need to know" doesn't mention a single thing about how to create one.
Literally in the video I have text for "how to make a heap" and then precisely tell you. Honest question, did you watch the video before writing this?
@@GregHogg"How to make a heap" is a lie. It says nothing about how to do that. All it says is how to use one already made for you.
Nice vid, whats written on top of your hat?
Devin is gonna know
and how is it different from a binary tree?
It is often visualized as a binary tree :)
@@GregHogg i understand, but how is it different?
@@ramalshebl60The rules to how those trees are build. Don't quote me on those time complexities tho.
The binary tree doesn't really have a rule except that each parent has a max of 2 children.
No sorting whatsoever, not recommended if you want to sort or search for values later on, as it's not better than the list it started with.
Adding, deleting and searching in O(n). Generally just not worth it.
A search tree is a binary tree with the added rule that each element of the left subtree of a node is smaller/eq than the root and right subtree larger.
Unbalanced: adding, deleting and searching in O(n).
Balanced: everything in O(log n)
A heap only says that all elements of the next level must be smaller (max heap) or bigger (min heap) and that a heap musst be complete aka. The tree is filled to the max, except the last "row" (standard binary heap, there are others).
Time complexities as shown in the video. Sorting in O(n log n).
@@JCel thanks for posting a reply even though my comment was a month ago; your reply certainly helped
This sounds awfully like a stack, whats the difference?
Does this really sort an array in O(n) ? 😅
It is true, that heapifying an array is O(n), but the resulting array is not necessarily sorted.
a heap is not an array it's a binary tree
it does...it might look like nlogn but the leaf nodes are not being compared which are half and if you calculate like that you can prove that not every node needs log n comparisons thus n
Turns out this is most likely not what most people wanted to know about the heap. It surely wasn't for me.
Well that's all there is to know about it so I guess you really don't care about them lol
Well I still don't know wtf a heap is but hey cool vid ig
To whomever it may be of concern,
Bear in mind that the O(n) complexity for the heapify process does not include the beforehand sorting of the array.
you can heapify in O(n) time without sorting iirc
@@memelord4639 yes, but not max/min heaps
no you can build both min and max heaps in O(n) time complexity@@emirmustafic786
Rip people who watch this and think heaps fully sort arrays
Yeah, I know my phrasing was a little misleading. It partially sorts enough to force it into a heap
Lol Ive read it as неар
Why is it log n to do an insert ?