תור ישראלי

במדעי המחשב, תור ישראלי הוא מעין תור עדיפויות, בדומה לתור עדיפויות רגיל, תור ישראלי הוא מבנה נתונים מופשט התומך בהכנסה עם עדיפות, הוצאה והצצה. הייחוד בתור הישראלי מגיע מאופן ההכנסה: עבור כל איבר שרוצים להכניס לתור, ראשית בודקים האם אחד מהאיברים בתור הוא "חבר" של האיבר שרוצים להכניס, אם כן, האיבר החדש יוכנס במיקום לאחר ה"חבר". אם אין לאיבר "חבר" בתור הוא יוכנס לסוף התור. בגרסאות מסוימות האיבר יוכנס לאותו מקום בדיוק כמו חברו (ולא לאחריו). אם תכונת החברות היא טרנזיטיבית אז כל החברים בתור של האיבר שרוצים להניס "יוקפצו" למיקום החבר הראשון בתור.

היתרון של תור זה בא לידי ביטוי במקרים שהמערכת צריכה משאבים זהים ע״מ לשרת אובייקטים ׳חברים׳, במצב כזה עדיף לשרת את כל ה׳חברים׳ ברצף ולא לשחרר משאבים ולאחר מכן להקצותם מחדש.

הקצאה ושחרור של משאבים הן פעולות יחסית יקרות ומתכנת טוב שואף לעשותן כמה שפחות.

תור ישראלי
סיבוכיות מקום וזמן
	ממוצע במקרה הגרוע
זיכרון:	$\ O(n)$ $\ O(n)$
חיפוש:
הכנסה:	$\ O(n)$ $\ O(n)$
הוצאה:	$\ O(1)$ $\ O(1)$
הצצה:	$\ O(1)$ $\ O(1)$

מימוש לדוגמה

# each item has a value and a list of friends

class Israeli_Queue:
    def __init__(self):
        self.queue = []

    def add_item(self, item):
        for i, val in enumerate(self.queue):
            if val.is_friend(item):
                self.queue.insert(item, i + 1)
                return
        self.queue.append(item)
            
    def peek(self):
        return self.queue[0]
    
    def pop(self):
        return self.queue.pop(0)

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

38925646תור ישראלי