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

You're very welcome!

Lolol lol thank you I think 😂

@@GregHoggthose are called voice cracks

Thank you greatly, and of course I will :)

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.

My pleasure!

Was actually considering doing that, thank you for the suggestion :)

You da man@@GregHogg

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

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.

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

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

Well that's all there is to know about it so I guess you really don't care about them lol

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

Yeah, I know my phrasing was a little misleading. It partially sorts enough to force it into a heap