Press enter to see results or esc to cancel.

Israeli Queues: Exploring a Bizarre Data Structure

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.

Source: The Houston Chronicle

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.

Defining simple priority queues

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

Source: Wikipedia

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.

Source: MemeCenter

This emergency room scenario demonstrates the simple idea of priority queues that we’ll try to improve upon with Israeli queues.

The need for grouping

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.

Source: GIPHY

 

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.

Use case: situations with high set-up costs

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.

The algorithm

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:

 

screen-shot-2017-01-11-at-11-58-48-am
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.

Comments

28 Comments

Continue Reading

… [Trackback]

[…] Read More on|Read More|Find More Informations here|There you will find 99769 additional Informations|Informations on that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

book of ra deluxe

… [Trackback]

[…] Read More here|Read More|Find More Infos here|Here you will find 91823 additional Infos|Informations on that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

DMPK Studies

… [Trackback]

[…] Read More here|Read More|Find More Infos here|There you will find 77629 additional Infos|Infos on that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

car crash

… [Trackback]

[…] Find More here|Find More|Read More Informations here|Here you will find 44639 additional Informations|Infos to that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

salary calculator

… [Trackback]

[…] Find More here|Find More|Read More Infos here|There you can find 55049 additional Infos|Informations on that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

kari satilir

… [Trackback]

[…] Find More on|Find More|Read More Informations here|Here you can find 80594 additional Informations|Infos on that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

Corporate Events Vendors in Hyderabad

… [Trackback]

[…] Find More here|Find More|Find More Informations here|Here you can find 99302 more Informations|Infos on that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

www.office.com/setup

… [Trackback]

[…] Find More on|Find More|Read More Informations here|There you will find 46425 more Informations|Informations to that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

jogos friv

… [Trackback]

[…] Find More here|Find More|Read More Informations here|Here you can find 29056 additional Informations|Informations to that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

italian citizenship

… [Trackback]

[…] Read More here|Read More|Find More Infos here|There you will find 10737 additional Infos|Infos to that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

camp cooking equipment

… [Trackback]

[…] Read More here|Read More|Read More Infos here|Here you will find 68615 more Infos|Informations on that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

agen bola

… [Trackback]

[…] Read More here|Read More|Find More Informations here|There you will find 6266 more Informations|Informations to that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

mold removal

… [Trackback]

[…] Find More here|Find More|Read More Infos here|There you will find 95442 additional Infos|Infos on that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

agen sbobet

… [Trackback]

[…] Read More on|Read More|Find More Infos here|There you will find 18588 additional Infos|Infos to that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

visto

… [Trackback]

[…] Read More here|Read More|Find More Infos here|Here you will find 18842 additional Infos|Informations to that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

cpns 2018 simalungun

… [Trackback]

[…] Find More here|Find More|Find More Infos here|Here you will find 57223 additional Infos|Infos on that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

Cheap last minute holidays

… [Trackback]

[…] Find More here|Find More|Find More Informations here|Here you will find 98785 more Informations|Informations on that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

see more

… [Trackback]

[…] Read More here|Read More|Read More Informations here|Here you will find 88115 additional Informations|Informations on that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

make money with a iphone

… [Trackback]

[…] Find More on|Find More|Read More Infos here|There you can find 54377 more Infos|Informations on that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

see this page

… [Trackback]

[…] Read More here|Read More|Find More Infos here|Here you will find 17077 more Infos|Infos to that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

Hyderabad Events Company Stix

… [Trackback]

[…] Read More on|Read More|Find More Informations here|Here you will find 86240 additional Informations|Informations on that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

agen domino qq online

… [Trackback]

[…] Find More on|Find More|Read More Informations here|Here you will find 11412 additional Informations|Informations to that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

Agen Bola

… [Trackback]

[…] Find More on|Find More|Find More Infos here|There you will find 18100 more Infos|Informations to that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

Software klinik

… [Trackback]

[…] Read More on|Read More|Find More Informations here|There you can find 63064 more Informations|Infos on that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

Aws alkhazrajii

… [Trackback]

[…] Find More here|Find More|Read More Informations here|Here you can find 61070 additional Informations|Informations on that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

free porn videos

… [Trackback]

[…] Find More here|Find More|Read More Informations here|Here you will find 49488 additional Informations|Informations to that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

paintless dent removal school

… [Trackback]

[…] Read More on|Read More|Find More Infos here|There you can find 42554 more Infos|Infos to that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]

Mode in großen Größenfür den Winter

… [Trackback]

[…] Find More on|Find More|Find More Informations here|Here you will find 75635 additional Informations|Informations on that Topic: blog.rapidapi.com/2017/01/11/israeli-queues-exploring-a-bizarre-data-structure/ […]


Leave a Comment

Tell us your thoughts!

Spread the API ❤️