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 :)

Some tips on adjusting to a new location

I have to first say that my blog is slowly shifting towards new topics. I had originally written this blog with a mathematical focus in mind but as I slowly entered the work force and began professional life, I have seen a lot of value documenting some of my struggles. In fact, because I graduated somewhat sooner than most of my friends, I find myself being somewhat of an expert on the job search, a lot of strategies which I used during my own job search a few months ago. In any case, I hope that I'll be able to more consistently write posts on mathematics that I see in the world but for now, these recent posts are some that I felt like documenting.

Since the move to Edmonton, I have been really homesick. In fact, it even culminated in flying back home one weekend just to see friends and family that I haven't seen in a few weeks. Now that I'm back though, I don't feel as homesick as before and there's really a couple reasons why. This post is going to explore some of those reasons:

1. Coworkers

One source of comaderie I get is from my coworkers. This is an obvious place to create friendships because you see your coworkers every day. In fact, I read that you will like your job more if you make a friend at work. It's not that I need a motivation to like my job more, rather, it is that extra something to make you enjoy going to work and it may even increase your opportunity to do things together after work or on the weekend.

Of course, the big problem with working at the Alberta Law Libraries is every coworker is female and they all have families and established lives. As opposed to a university setting where people are around my age, have similar interests and are at the same place in their lives (just beginning their professional careers and don't have families to go home to), I'm at a place where my coworkers all have families and they really don't have time to 'hang out'. It's something unfortunate that I didn't really think of when taking the job but certainly not a deal breaker; I really would have liked to have coworkers around my age and at the same place in their lives.

Despite all this, my culinary interests and age fit right in with the coworkers I have. I don't think I'm as good as I think I am and I think there is some bias but I do think that all the things I cook taste really good (yes, probably bias). This interest in food has definitely led to some interesting conversations around the office.

I think it's funny that my age fits right into the conversations we have: as I mentioned, most of my coworkers have families and a lot of their children are around my age. Often times, they'll make some statement about the youths of that age and I sit there, almost amused, at the observations they make.

2. Sports

This is a two in one combo - it's a great way of keeping fit and also meeting new people. For example, the University of Alberta has a great selection of sport clubs to be a part of. You really have to dig around for information yourself if you want to find the clubs that you can participate in. Sometimes even after finding all the necessary information, you don't have the right equipment to play with (my racquet is back in Van). I suppose I should have brought it with me or even brought it over the time I went back to Van but I just totally forgot.

I do think however, this is a really good option for the two reasons above - it also helps that there is a University club because it is more than likely that the people playing there will be around your age (though they may not be at the same place in their lives with work).

3. Professional Organizations

During my job search, I talked about how important it was to network with your contacts and find jobs through your network. Not only are a lot of the jobs not usually posted on sites like indeed or simplyhired, but recruiters will often rely on referrals from coworkers or trusted people to hire people for the job.

I was fortunate enough to be a part of the Toastmasters International Organization when I was in Vancouver and when I moved over to Edmonton, I immediately thought of joining a Toastmaster club. Not only would it be a chance to meet some new people, but it would be a good chance to practice my public speaking and leadership skills. Just doing a google search on Toastmasters and Edmonton brought up numerous groups and I, wanting to be more efficient with my time, decided to join one at 7 in the morning before work. Needless to say, the days I go to Toastmasters are very long days. This seemed to be the most successful way of meeting people because the first time I went, I said that I was interested in networking and a fellow Toastmaster invited me out to a networking event on that same day. I was late to the networking event, plus my networking skills aren't that great but I did get to meet a few people there and had some really good conversations.

As an aside, I was also thinking about joining a professional product management organization - I think that that is what I will be doing eventually in the future.

4. Meetup!

I remember after reading through many tech articles, reading about a site called Meetup but I never gave it much thought because I was in Vancouver at the time and had plenty of things to do. One day, a coworker no less, suggested to me that someone she knew who was new to Edmonton had looked online and found a group of other people who were 'New to Edmonton'. It was a good way of meeting others with similar interests (in this case, everyone was new to Edmonton). She sent me a link to the meetup.com site and I checked out all the meetups in Edmonton. Some look quite interesting, in fact, so interesting that I have joined the Chinese and Japanese group. So far, I haven't been to any of these meetups but I know that once I get into these meetups and become a regular member, I will at least have some sort of base that I can connect to.

These are just a few of the strategies you can use to meet new people and to try to establish a new base of friends to hang out with. Between work, Toastmasters, working out several times a week and trying to figure out which meetups to go to, you can tell I've been busy.

Have you moved to somewhere new? How did you cope and adjusted to it? How did you meet new people?