Priority Queue JavaScript Data Structure
In this lesson, you'll learn how we can combine several queues to create a new data structure: a priority queue. A priority queue allows the user to add items to the queue that are deemed to be high priority, and get moved ahead in the line. This added complexity is simple to achieve and is a good example of how we can build up complexity through the use of data structures.
Instructor: [00:00] We can easily make a PriorityQueue by using two queues, a high priority queue and a low priority queue, together.
[00:07] Our API will be the same as a normal queue. We'll have an enqueue, dequeue, peek, and is-empty method, as well as a length property, but we'll make some modification.
[00:17] First, we'll create two queues that we store in closure, a low priority queue and a high priority queue.
[00:23] Next, our enqueue method receives a second argument to indicate that an item is high priority. We'll set it to false by default. If an item is deemed high priority, we put it in the high priority queue. Otherwise, it goes into the low priority queue. We'll use a turn area to determine which priority queue it should go into.
[00:43] Next, our dequeue method will make sure that the high priority queue is empty before it dequeues from the low priority queue. This ensures that all high priority items are dequeued first. This time, we'll use an if statement to early return from the high priority queue, or otherwise return from the low priority queue.
[01:04] Next, our peek method gets a similar change. Just like we dequeue from the high priority queue first, we're going to peek from the high priority queue first as well. In fact, I can copy-paste this code and just make a change to which method is being called.
[01:18] Next, our length property is the addition of each queue's length property.
[01:24] Lastly, our is-empty method is the conjunction of the two queues' is-empty methods.
[01:30] Now that we've built our priority queue, let's try it out. Let's imagine your manager has given you a few tasks. A fix here, a bug there, and a new feature to build here. If we take a peek at our queue as it currently is, the item we should get back is a fix here.
[01:48] Great. That's working as we expect. That fix here was pretty easy. Let's dequeue it and make sure that's worked as well. Great. We dequeued a fix here, and now we're on a bug there.
[01:59] Let's say our manager comes to us with an emergency task, a task that needs to be done right away. Normally, we couldn't put something at the front of our queue. It has to wait in line, like every other task. But, using the second argument in our enqueue method, we can put it to the front of the tasks we need to do. If I save this and we take a peek at our queue now, that emergency task should be what comes up.
[02:21] Let's say we've averted the crisis, we've solved our emergency task, and we're going to dequeue it. Let's make sure that's what we get back when we dequeue and see that we're back to a bug there being the thing we need to fix.
[02:33] Great. We dequeued the emergency task, and a bug there is what we need to do. On with our tasks for the rest of the day.
Hi DIYA, thanks for sharing this. You’re right that this is not a very robust solution, this was intended to demonstrate how something more complex could be constructed of simple elements. None of the implementations in this course are precisely how I would expect them to be implemented, as this is more about instruction and theory than it is about production ready code. That being said, you are correct that it might be cool to make a lesson on how to create heaps and make a more robust solution than this one in the future. Perhaps I’ll have to make an update or a Volume 2 for this series.
As an intermediate javascript developer this has helped me become more exposed to thinking like a programmer. I would agree though that if I were a newcomer or beginner venturing out into my programming career, it would be hard to understand the "why"s here, but thank you so much for a great tutorial! As for DIYA's comment, i'm interested to see a real world example now. A second course (volume 2) would be great Kyle!
Hi, got "TypeError: createQueue is not a function" when I try to use your code in VsCode, don't see what I am missing ?
Update: It works when I do "exports.createQueue = function createQueue()" in "index.js" but would like to know how you do the trick on your side ?
No trick, probably a broken export import situation. I will look into it later when I’m on my computer and not my phone.
This is awesome stuff Kyle. Though I understand Diya concerns, I think this is a huge step in the right direction. I have been a JS pro for the last 12 years though I did not finish the CS training. You made me feel less dumb today. Let's all remember the first day our Math professor was adding letters and numbers together and tried to convince us that: x + 2 = y; Jokes aside what am advocating for is more empathy towards the beginner and intermediate. If this is not production ready, hell now I'm motivated and excited to dig deeper and find out what is. This really made the egghead subscription worth it.
Hi, I'm not sure if this is the right way to teach priority queues in case newcomers to data structures and algorithms are watching this. I mean the idea is more or less correct but we don't really implement priority queues like this. In fact in the real world, you'll most implement priority queues using hash tables or binary heaps. With the above method, you cannot do things like: changing priorities, fetching data according to specific priorities etc. It's not that something like you've shown can't exist but it's not how it's done in the "industry". At least I've never seen a priority queue being implemented like this and I've interviewed in as well as used quite a bit of ds and algos at work. Maybe, in addition to this, you can showcase priority queues being implemented with hashing or heaps.