Priority Queue Min Heaps and Max Heaps 

Yes, he means this would still result in a min heap though his previous slide makes it sound like the goal of the negation is to create a max heap.

@@yutaitadori7318 lmao. Very productive.

i am new to ds but i think it is because to implement stable sorting

Because negating a zero still gives a zero.

As stated it's there to make the sorting algorithm stable.

When x == y , both the values are same. So which value comes out first doesn't make a difference. i.e x in case of x

I think the simplest way is to see it this way. Min PQ means that if x < y we poll x first then y. If x is equal to y, it makes no difference since they have same priority. We might as well poll x first then y. The rule becomes x y, we poll x first then y. f x is equal to y, it makes no difference since they have same priority. We might as well poll x first then y. The rule becomes x >= y. The point is that Min and Max PQ differ in their polling strategy depending on if x is greater than or less than y. When two elements have the same value, both strategies behave the same.

it won't make a difference.

If the earlier heap prioritized the max value, then largest number come out of the queue first. Zero would be the smallest number and come out of the queue last (assuming no negative numbers). If we negate everything to implement a min queue, Zero would be the largest number and come out of the queue first (since all the previously positive numbers are now negative).

Hey Chris, I think my slides are correct, let me explain. In a min PQ if x = y and now y is the smaller element and it should come out first.

Yes, the point here is to make sure you wanna get a min PQ, right ?

I think the confusing part is: if you do the negation thing, it results in the same thing as if you build a max-heap from the same numbers used in the min-heap. People are confused because its calles min-heap to max-heap, but after transforming, you still pull the smallest element first after the min-heap principle. Probably its just the naming of min-heap to max-heap. If its called "access min-heaps in reversal order", everything would be fine. And thats actually the same as building a max-heap from the original values.

@@xRandom112 but I still don't get if 13 is greater than 11, 11 should come out first as if x>=y, y comes out first. Can you or the video owner make this clear to me please?

@ismail bagga is it like after the negation, 2 becomes the largest number and 13 becomes the smallest so following the min heap property, 13 comes out first making this act like a max heap?