Use the heap module to implement a priority queue - Python Tutorial

- [Narrator] Let's start building out our priority queue class. So we start with the constructor. Double underscore in itself. And this time our list of elements is going to be called self.elements. With previous data structures we used self.items, but here I'm using self.elements. And you'll see why in a moment. Okay, so then we have a method called is empty. Take self. And then we're going to return, not self.elements. Okay, same logic as before. So an empty list returns false. So returning not, it will be true if it's empty. And again you can use the LEN version, but I'll let you refer to previous videos if you want to use that version. So if the length is zero, it's also empty. You can use that logic as well. So now we're going to do put so def, put, and we have self. But then there's actually two arguments here. So we have self and we have item and we have priority. So this is why I've used elements instead of item, because it's not just items in our list, it's actually items and their associated priority. So here we're going to do a heapq. Now this is from this heapq module, okay, so I'm referring to that module, .heappush. Self.elements. So it's pushing it onto that list. A tuple containing the priority and the item. So what does heapq.heappush do? Well basically it's going to push this element onto our priority queue and it's going to do so in such a way that it preserves the required ordering of our priority queue so that we would always be able to access the minimum value based on that priority that we've passed in. Then we're going to have a get method. And this is going to return heapq.heappop. And we're heappop self.elements. And it's going to be at index one. And we'll see why that is the case in a moment. Finally, we got def dunder str. And this as usual is to give us human readable representation of what's going on inside our objects. So we're going to return str of self.elements. Should have just taken Python's suggestion there. There we go. Okay. So let's have a look at how this works. So if dunder name is equal to dunder main, then we can start playing with our priority here that we've just built. So pg is equal to priority queue with capitals. So we now have an instant and we can start off just by printing where the pq is empty. Actually just sprint pq first, make sure that's working. Yep. So you can see it's just an empty list to begin with. And check that it's empty. Print pq.is. Ah, okay. And what's happened here is I haven't actually made it into a function call cause I haven't added the parentheses. So it's telling me that it's a bound method of the priority queue. However what I wanted to do there is to make it into a function call. Okay, and you can see here it's true, down in the terminal. That pq is empty at this stage. Okay so now it gets interesting. So let's just make a comment here. Item comma priority. So what are we going to be putting onto our priority queue? We're going to be putting two things. We're going to be putting a value and a priority associated with that value. So I want to pq.put. Let's have eat, with a priority of two. And then I'm going to do control D just to make it easier to type or to save typing. And encoding obviously has a priority of one, and sleep has a priority of three. Okay, so look what's going on here. We have an item. So that's the activity, eat, code, or asleep. And then depending on our prioritization of those, we assign a value. So I've done coding being most important, eating second most important, and sleeping third most important. Obviously that's not real life priorities, it's just for the purposes of demonstration. Now, if we were to print the priority queue at this stage, what do we get? So down in the terminal here, this line that I've highlighted, you can see that even though we put them in, in the order, eat, code, sleep, the way they've been displayed is code, eat, sleep. Now the only thing we can guarantee about this output is that the one with the highest priority will be at the left hand side, okay. At the front of the queue. The rest we can't guarantee where they're going to be. So in a longer list that would become relevant, but you can always guarantee that that first one is going to be the highest priority value which is what we want. So that's how that works. Then let's have a look at how get works. So print, pq.get. And let's do that a few times, three times. And you'll see that when we run that, each time, the way that we set out this is why on line 21, why I put that index after the self.elements, because there's two items in that elements tuple. And when I'm using get, I'm not really interested in the priority, that's being handled internally by the priority queue. I'm just interested in the value. So that means index with one of the tuple. That's the second item in the tuple. And finally, let's see what our protocol looks like. Here, once we've done all that. Okay, you can see it's back to being an empty list. So I just want to clarify something here. When we use put in terms of the interface that we've created then the value goes before the priority. But in terms of the way it's handled internally, you can see here that we have on line 18, the tuple is priority and then item. Okay. So just be aware of that. And the reason we did that is because the way heapq works is it goes in order through the tuple. So it looks at the first element first. But in terms of the interface it makes more sense to think about the item that we're passing in because we're not really worried about the implementation details. In fact, that is one of the key points about an abstract data type is that the inner workings of it are not really our business. All we need to do is to use the interface provided. In this case that's the methods for putting and getting. And also checking whether the priority queue is empty. Now we have a class we can use to create priority queues. I encourage you to experiment with the class and get comfortable with how it works before moving on to learn how this data structure is used in the A* algorithm.