Practical Applications of Priority Queues

A few weeks ago, my two week free trial membership to the downtown YMCA expired. On the last day, I went in to get my annual membership. The YMCA was just about to close at 7 and I figured I would have enough time to get my new membership and then head into the gym for a quick cardio workout.

I believe it was around 5:45 that I started waiting in line and since I wanted to head into the gym to do some cardio, I needed about half an hour. I didn't think that it would take that long, especially with 2 counters open and only 2 people ahead of me in the line. I didn't have the option to go into the gym to get my membership another day because my membership had already expired.

So, I diligently waited in line.

I waited. Waited some more. Then after I got tired of waiting, I waited some more.

It was like everyone ahead of me was signing up for a new membership and they all had some problem or another with the computer or with ID or what not.

It was then, as I was waiting in line, that I came up with a pretty great idea. READ: crazy.

Normally when we are lining up for something, the lines act a lot like queues from Computer Science; ie. they act on the FIFO principle. FIFO stands for First In First Out, in other words, if you are the first to arrive in the line, then whenever the service is available to you, you would be the first one out of the line.

My idea consists of using priority queues instead of queues. How are priority queues different from queues though and what would it mean if places that had lineups acted like priority queues instead of queues?

Priority queues are different from queues in the sense that they do not act on the FIFO principle (unless the priority was measured by how long an object first entered the queue - in the real world, it would mean that whoever has stood in line the longest would get service first, which is essentially the same as a regular queue / lineup nowadays)

Instead of acting on a FIFO principle, it 'chooses' its next object to exit the queue by way of some measure of priority. In the example above, the priority was based on time spent in the queue. Priority can also be measured by things like sorting the objects (an equivalent in real life would be prioritizing based on a sorting of last names in a line) and how important an object is (again, if you're at a hospital, you would get service first depending on how sick you are).

Okay, so what does that mean in the real world though? How do we assign priority in the real world?

Let me talk a bit about why I think a priority queue makes sense to me in the real world.

Imagine you're one of 10 people in the line. You are last in line (bummer!). There is only one counter open to service customers. To make matters worse, the guy in front of the line wants to do a task that you know, will take at least 1 hour. Everybody else in line (the 9 others including yourself) just want to complete a task that will take only a minute each.

I feel like it would make sense to assign some priority to the 9 other people whose tasks only take a minute each and then to give better service to the guy who needs to complete a 1 hour task.

Take a look at the total wait time between the two different scenarios:

1 hour
1 hour + 1 minute

..

..

1 hour + 8 minutes

compared to:

1 minute

2 minutes

..

..

8 minutes

Obviously the example is a bit contrived. If priority was only assigned based on how long (or short) of a task would take, people could keep coming in with 1 minute tasks and always be served ahead of the guy with a 1 hour task. Clearly, the priority needs to have 'input' from both how long the task would take as well as how long the guy has spent in the line.

In fact, it seems to get even more complicated as there are more counters open. (Well, technically if there were 10 counters open then everybody would get serviced and it would make the solution easy).

Caveat:

This certainly isn't an idea that I have fleshed out a lot. I do know that the priority function would take in both the time spent in the queue (people can't wait forever) and the importance of the task as values (by servicing those with small tasks first, wait time overall would be decreased) and then output a priority but I'm not sure what other values it would rely on as well. There would also be real time updating of the priority as people waited and entered the line.

What do you think of the priority queue as a real life application? I'm not even sure how that would work at somewhere like the bank though I could imagine some fairly crazy scenarios of how a bank might implement something like that:

Imagine a kiosk that you would go to at the start of the line where you would input your task. The kiosk would then output a ticket with a number (kind of like at shopping markets). You would take a seat and then wait until the bank displays your number above a counter. As people file in, they are given numbers as well but the priority is changed for both them and existing members of the queue. As counters open up, customer service representatives would press an 'Open for Service' button and the algorithm in the background would choose the customer with the next highest priority to be served.

This could even go a bit further, if customers needed more than a certain amount of time to be serviced (say 1 hour) then the computer would tell them as such and estimate a time when they could come back. If they don't like that option, they could even have the option to schedule an appointment with a separate customer service rep to get the best service possible.

Just something to think about :)