This morning, I stumbled upon a data structure called an Israeli Queue. As I’m flying to Israel tomorrow, I had to check it out. It turns out that the Israeli queue data structure isn’t just a punny data structure, it’s a useful one too.
Israel is notorious for extremely unorganized queues or lines. I can say that–I’m from there. Because of the disorganization, people tend to find their friends and wait in line with them. Similarly, an Israeli queue data structure is based on grouping and prioritizing items based on “friendships.” Here’s how it works.
The idea behind priority queues is pretty simple: you have a collection of items / tasks that need to be performed, and you can pull out one item at a time. When inserting items into a priority queue, you attach a priority to each item. When pulling those items out (dequeuing), the item with the highest priority at that point will get dequeued. Here’s an example of a first-in, first-out (FIFO) queue (prioritized by time of entry).
An example for the use of priority queue could be the queue for an MRI scan in a hospital.
Imagine the following scenario*:
* Following example based on my binge watching House MD and thus is probably not medically correct. Be warned.
Patient 1-Abdominal pain: The first person waiting is a patient with unexplained abdominal pain. The doctor recommends an MRI to see if there are any problems, but it’s not urgent as the situation is not life threatening. The patient is placed in the queue for the MRI with a low priority of 1.
Patient 2-Lung cancer: Another patient arrives with suspected lung cancer. A lung MRI is required to confirm the diagnosis and start treatment. The faster the treatment starts, the higher his chances of healing are. He’s placed on the queue with priority 5, bumping him to the top.
Patient 3-Car accident: But then, a car accident occurs. A critical patient comes in and requires an MRI to locate an abdominal bleeding. As this condition is immediately life-threatening, she is enqueued with a 10 priority.
This emergency room scenario demonstrates the simple idea of priority queues that we’ll try to improve upon with Israeli queues.
Let’s introduce a new concept – friendship between items on the queue. Items can be friends if they are somehow related and if it makes sense for them to be performed together.
Imagine the lung cancer patient from the previous scenario has also been complaining about mild headaches. The doctor recommends a head MRI scan and, as the issue is not urgent nor immediately life-threatening, assigns it with a low priority of 1.
We can think of the patient’s (let’s call him Patient X) two required scans as ‘friends’. These are two separate scans: one in the lungs and another in the head. However, if Patient X is already admitted and in the imaging wing for his higher priority lung scan, the doctor might as well do the head scan at the same time. Those two tasks are friends.
The reason doing both a high priority and low priority scan simultaneously makes sense is because the cost to do both at once is lower than doing each separately. Why? We can think of both of these tasks’ costs as composed of two parts:
Set-up cost – the cost of preparing for the task, which is shared amongst friend tasks
Execution cost – the cost of actually executing the task.
In the MRI scan, the set-up cost includes bringing the patient in, instructing him, asking some questions and explaining the operation. The execution cost is the actual scan.
For friend tasks, the set-up cost is only deducted once. In our MRI example, even if we do five scans, as long as they are on the same person (and thus, friend tasks), we only ‘pay’ the set-up cost once. However, we still pay the execution cost five times.
Since the set-up cost is only deduced once in an Israeli queue, if set-up cost is high, it may make sense to group together friend tasks. Another example of this is industrial printing. Imagine a case where you have a monochromatic manual printer. You can put one color in it at a time, and print in that colour. You get a lot of orders, and each has a different priority (e.g. “We need those flyers ready for a parade tomorrow” vs. “we need that newspaper printed by the end of the week”). However, it takes time to switch the colour in the printer–that constitutes the setup cost of those tasks. Thus, it may make sense to make jobs of similar colors ‘friends’ and perform them all together.
We’ll start off with a basic priority queue, making two critical changes:
1) Groups: Instead of just containing items, the queue will contain groups of items. Groups may have one or more items in them, but cannot be empty. They may be organized in order (by priority) or not. A group will only contain enqueue items that are friends.
2) Enqueueing: When enqueueing a new item, we’ll iterate over all the groups in the queue. If the item being inserted to the queue is friend with an item in any of the group (friendship is a transitive relation, so if he’s friend with one, he’s friend with all), the item will be added to the group and its priority will be added to the group’s priority (group priority is sum of its members).
Here’s the pseudo code:
And there you have it! It actually turns out pretty useful.
Has anyone used an Israeli queue before? Or have an actual code snippet or example you’d like to share? Let me know in the comments below.
We're thrilled to announce the latest update to the Rapid Enterprise API Hub (version 2024.3)!…
Are you curious about what your API consumers are searching for? Is your Hub effectively…
The RapidAPI team is excited to announce the February 2024 update (version 2024.2) for the…
This January's release brings exciting features and improvements designed to empower you and your developers.…
Rapid API is committed to providing its users with the best possible experience, and the…
In today's fast-paced digital world, APIs (Application Programming Interfaces) have become the backbone of modern…
View Comments
Thanks for the detailed explanation,
I was able to implement it in C#.
There is no mention of Dequeueing though-
Is Dequeuing only possible in groups?
What would dequeueing a single item involve?