Welcome back. Today we're going to talk about turning min priority queues into max priority queues. This is part two, a five in the priority queue series. So you may already be asking yourself, why is it important that I know how to convert a main priority queue into a max priority queue? Well, here's the problem, often the standard library of most programming languages, they will only provide you with either a max primary key or a min priority queue. Usually, it's a main priority queue, which sorts elements by the smallest element first, but sometimes we need the max priority queue depending on what we're programming.

So how do we do this? How do we convert one, one type of priority queue into another type? Well, a hack we can use is to abuse the fact that all elements in a priority queue must implement some sort of comparable interface which we can Simply negate or invert. To get the other type of heap. Let's look at some examples. Suppose for a moment that we have a priority queue consisting of elements that are on the right side of this screen, and that these are in that main priority queue.

So if x and y are a numbers in the priority queue, and x is less than or equal to y, then x will come out of the priority queue before y. the negation of this is x is greater than or equal to y. And so y then comes out before x, because all these elements are still in the priority queue. Wait a moment you say, isn't the negation of x is less than or equal to y, just x greater than y and x is greater than or equal to y? Well not for competitors. You see if x is equal to y, whether or not the competitor is negated, x should still equal y. So now let's see what happens when we pull all these elements of priority queue with our negated competitor.

So first, we would get 13, because the greatest next ones 11 753, and two. An alternative method for numbers is to negate the number before you insert it and negate it again, when it comes out. This is a hack, specific to numbers, but it's pretty nice. So let's see how that works. So let's negate all the numbers inside our priority queue. And now we can see that definitely minus 13 is the smallest so should come out first.

So minus 13, indeed comes up first. But now we have to renew the data and we have 13 Everything is good so far. Next is minus 11. So really positive 11 and so on my a seven, seven, and so on just so keep pulling and then a ring get the value to get it out of the priority queue. It's a pretty neat hack. Okay, now let's look at another examples using strings.

So suppose Lex is a competitor for strings, which sorts strings in lexicographic order. This is the default for most programming languages, then let's call n lacs be the negation of blacks. And also let's assign s one and s two to be some non null strings. So below you can see that our competitor assigns minus one if s one is Less than less to lexicographically zero should equal lexicographically and plus one if s one is greater than s two lexicographically. And then n lacks is just the negation of that. So just to break it down like sorts, strings Lexa graphically, but we're interested in gaining lag so that longer strings appear before sort of shorter strings and also that strings with letters at the end of the alphabet appear before those containing letters.

At the beginning of the alphabet, I think I said that right. This was in effect turn a man he into a maxi. Let's look at a concrete example. So by adding all the numbers on the right to a prior q with the lexicographic competitor, here's the ordering we should expect. First, we get a because it's a shortest string that has characters appearing closer closest to the start of the alphabet, then it comes up B, then f Zed, then x then x R and x x. So now let's do the same thing but with n likes.

And we should hopefully obtain the opposite sequence in reverse order. And then we get x x x r, x, f, Zed, B and A. So it did exactly what we intended to do. So that's all there is to converting min heaps to max heaps or max heaps and heaps vice versa. You guys are now pros. You're awesome.

In the next video, we're going to look at how to add elements to a prayer queue. Also, if you're interested in the story, Code implementation for priority queue, check out the link below at the bottom of the screen. I should also have a link in the description to the GitHub repo with all these data structures. Guys, thanks for watching. I'll catch you next time.