What is a priority queue?

13 minutes
Share the link to this page
Copied
  Completed
You need to have access to the item to view this lesson.
This is a free item
$0.00
د.إ0.00
Kz0.00
ARS$0.00
A$0.00
৳0.00
Лв0.00
Bs0.00
B$0.00
P0.00
CA$0.00
CHF 0.00
CLP$0.00
CN¥0.00
COP$0.00
₡0.00
Kč0.00
DKK kr0.00
RD$0.00
DA0.00
E£0.00
ብር0.00
€0.00
FJ$0.00
£0.00
Q0.00
GY$0.00
HK$0.00
L0.00
Ft0.00
₪0.00
₹0.00
ISK kr0.00
¥0.00
KSh0.00
₩0.00
DH0.00
L0.00
ден0.00
MOP$0.00
MX$0.00
RM0.00
N$0.00
₦0.00
C$0.00
NOK kr0.00
रु0.00
NZ$0.00
S/0.00
K0.00
₱0.00
₨0.00
zł0.00
₲0.00
L0.00
QR0.00
SAR0.00
SEK kr0.00
S$0.00
฿0.00
₺0.00
$U0.00
R0.00
ZK0.00
Already have an account? Log In

Transcript

All right, welcome back. Today we're going to talk about everything to do with priority queues from where they're used to how they're implemented. And towards the end, we'll also have a look at some source code. Along with all the priority queue stuff. We're also going to talk about heaps, since both topics are closely related, although not the same. So the outline for the priority queue series, is we're going to start with the basics of working about what are priority queues and why they're useful.

Then all find some common operations we do on priority queues and also discuss how we can turn min priority queues into max priority queues followed by some complexity analysis. And we'll talk about common ways we have implemented priority queues. Most people think heaps are the only way we can implement a priority queue. That priority queues somehow are heaps. I want to dispel that confusion. Next we're going to go into some great detail about how to implement the priority queue using a binary heap.

There, we'll look at methods of sinking and swimming nodes up and down our heap. These terms are used to can shuffle around elements in a binary heap. As part of the implementation explanation, I'll also go over how to pull and add elements. So there's a lot to cover. So let's get started. discussion and examples.

This is going to be part one of five in the priority queue series. So what is a priority queue? a priority queue is an abstract data type that operates similar to a normal queue except for the fact that every element has a certain priority. So elements with a higher priority come out of the priority queue first. As a side note, I'd like to remark that priority queues only support elements that are comparable, meaning that data we insert into the priority queue must be ordered in some way either from least to greatest erased lease. This is how we can assign relative priorities between elements.

Okay, let's go into an example. So suppose we have all these values that we inserted into our priority queue on the right. And then we impose an ordering on the numbers such that we want to order them from least to greatest. So the smaller numbers have a higher priority and the bigger ones, so they will be removed from the priority queue first. Suppose we have now a list of instructions. So what the pole operation means is Remove the element that has the highest priority in our priority queue.

So let's see how this works. So if I say, Paul, then I remove the element with the highest priority, which happened to be one. Now I say add two. So we add to to our priority queue, and poll. So next, we polled the smallest elements in our priority queue. And that happened to be the two we just added.

Next, we add for all the smallest, this is three, add five, oh, also add nine and then pull the rest. So as I pulled the RAS, I'm continuously grabbing the smallest element and the priority queue. So it turns out that as we added, and pulled numbers, we got an ordered sequence. This is a coincidence, actually, as we added pull numbers from the priority queue with that Do not necessarily end up getting an ordered sequence, we are only guaranteed that the next number that is removed from the priority queue is the smallest number that was currently in the priority queue. So how does the priority queue know, which is the next smallest number to remove? As humans, we could see the numbers visually inside the priority queue and look and know what one was the smallest the whole operation was going to return.

But fundamentally, how does the machine know this? Does it resort all the elements inside the priority queue before each pull operation? No, in fact, that would be highly ineffective. Instead, it uses what is called a heap. So the next big question then is what is a heap? Usually I make up my own definitions, but I really liked the song From wiki, a heap is a tree based data structure that satisfies the heap invariant, also called the heap property.

If a is a parent node of B, then A is ordered with respect to B for all nodes A and B in the heap. What this means is the value of the parent node is always greater than or equal to the value of the child node for all nodes. Or the other way around that the value of the parent node is less than or equal to the value of the child node for all nodes. This means we end up getting two types of heaps, Max heaps and min hits. So max heaps are the one with where the parent node is always greater than its children and the min heap is the opposite. So both of the following are actually binary heaps binary because every node has exactly two children.

The children cannot see or no values I have not drawn in. So why are we interested in heaps? Well, heaps form the canonical underlying data structure for priority queues. So much so that priority queues are sometimes called heaps, although this isn't technically correct, since the priority queue again is an abstract data type, meaning it can be implemented with other data structures also. Okay, we're going to need to play a little game, I'm going to give you some structures. And you need to tell me whether it is a heap or not.

So inspect the following structure and try to determine whether it's a heap or not. You can pause the video if you like. But I'm just going to give you a short moment here. No, we have a violation of the heap invariant and this tree so it's not a heap. Is this structure a heap? Yes, it is a heap because it satisfies the heap invariant, and it is a tree.

So we often see heaps like these and why we're called binomial heaps. Note that heaps aren't necessarily binary heaps, they can have any number of branches. On to our next one. So is this a valid heap? Yeah, it's a valid heap. Because even though this one is strangely, strangely structured, we're free to move around the visual representation of the nodes as we please.

So yeah, it's a valid teep. How about this one? No, this structure is actually not even a tree because it contains The cycles, all heaps must be trees. What about this one? Yeah, it's a heap. What about this one?

Also heap because it satisfies the heap invariant that all all nodes are less than or equal to or greater than or equal to its parent. How about this one? No, it's not a heap because it does not satisfy that heap invariant. However, if we do change the route to be 10, then we can satisfy the heap invariant via a mean heap or rather sorry, a max heap. So when and where is a priority queue and a heap use Probably one of the most popular places we see priority queues is in dexterous shortest path algorithm to fetch the next nodes we explore. priority queues are really handy anytime you also needed behavior in which you need to dynamically fetch the next best or the next worst element.

They're also used in Huffman encoding, which is often used for lossless data compression. Many best first search algorithms use priority queues in their implementation to continuously gain grad The next most promising node in the graph as it's being traversed. And finally, we also see priority queues in prims minimum spanning tree algorithm on directed graphs. So it seems priority queues are really important, especially for graph theory algorithms, which is where we see them often. Okay, onto some complexity with priority queues implemented as a binary heap. To begin with, there exists a method to construct a binary key from an ordered array in linear time.

We're not going to cover this algorithm but it's pretty cool. And it forms the basis for the sorting algorithm heapsort. Next is pulling and, or rather removing pulling or removing an element from the root of the heap. This takes logarithmic time, because you need to restore the heap invariant, which can take up to logarithmic time. So peeking or seeing the value at the top of our heap can take constant time, which is really nice. Adding an element to our heap takes logarithmic time, again part because we possibly have to reshuffled heap by bubbling up the value as we will see in a later video.

Then there are a few more operations we can do on priority queues. So removing a an element, which is not the root element. So the naive way of removing an element in the heap is to do a linear scan, find the items position and then remove it. The problem with this is it can be extremely slow in some situations, especially if you're removing a lot. But generally you don't do this and it's not a problem, which is why most implementations are just lazy into the linear scan solution. However, there does exist a way to reduce the removing time complexity, which I will go over later in the later video in great detail in this video series.

So stay tuned for that this method uses a hash table to reduce the removing time complexity to be logarithmic, which is super critical. Actually. If you're Removing as much as you are adding. Now the naive method to check containment within a heap. binary heap is linear. Again, you just scan through all the elements.

But with the help of a hash table, we can reduce this to be a constant time, which is super neat, especially if we use the hash table implementation for the removing speed up and we get as a free bonus. The downside however, to using hash table implementation is that it does require an extra linear space factor and it does add some constant overhead because you're accessing your table a lot during swaps. So I implemented a priority queue using a binary heap with the complexities I have outlined the last two slides which you can check out at the URL provided below. I'll be creating a video going over the source code after I finish explaining everything to do with priority queues. So stay tuned for that. Thank you for watching and see you in the next video.

There's still a lot to cover in the topic of priority queues.

Sign Up

Share

Share with friends, get 20% off
Invite your friends to LearnDesk learning marketplace. For each purchase they make, you get 20% off (upto $10) on your next purchase.