תור עדיפויות

במדעי המחשב, תור עדיפויות (או, בשם אחר, תור קדימויות, באנגלית: Priority Queue) הוא מבנה נתונים מופשט המיישם לוגיקת תור, אך אינו מבוסס כתור רגיל על סדר הכניסה בלבד (באנגלית: FIFO - First In First Out), אלא הוא מבוסס על קוד עדיפות (באנגלית: priority), המסופח לאובייקט המוכנס לתור וככל שערך קוד העדיפות של האובייקט גבוה יותר (לפי סדר מלא כלשהו על קבוצת הערכים המשמשים לסמן את העדיפות), כך יקודם מקומו בתור (מיד עם כניסתו).

פעולות על מבנה הנתונים

תור עדיפויות תומך בפעולות הבאות:

• הכנסה עם עדיפות - ערך יוכנס לתור לפני הערך עם העדיפות הגבוהה ביותר בתור, שעדיין נמוכה מהערך המוכנס, לפי סדר המלא שהוגדר.
• הוצאה - הערך עם העדיפות הגבוהה ביותר לפי יחס הסדר המלא שהוגדר, יוצא מהתור.
• הצצה - הערך שהיה מוצא מהתור אם הייתה מתבצעת פעולת ההוצאה יוחזר, מבלי שיוצא מהתור. כמו במחסנית, גם בתור עדיפויות פעולת ההצצה היא אופציונלית, וניתנת למימוש על ידי שילוב של הוצאה והכנסה.

אפשר להגיד שתור פשוט הוא מקרה פרטי של תור עדיפויות, כשהעדיפות נקבעת לפי סדר ההכנסה לתור. באופן דומה, מחסנית היא מקרה פרטי של תור עדיפויות. עם זאת, בפשטות ההגדרה של העדיפות במקרים של תור ומחסנית מאפשרים מימוש יעיל יותר מזה של תור עדיפויות כללי.

ניתוח סיבוכיות

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

• רשימה מקושרת ממוינת: במימוש כזה, ההכנסה תתבצע בסיבוכיות $\ O(n)$, ואילו ההוצאה או הצצה - בסיבוכיות $\ O(1)$.
• רשימה מקושרת לא ממוינת: במימוש כזה, ההכנסה תתבצע בסיבוכיות $\ O(1)$, ואילו ההוצאה או הצצה - בסיבוכיות $\ O(n)$.
• ערימת פיבונאצ'י: במימוש כזה, ההכנסה או הצצה תתבצע בסיבוכיות $\ O(1)$, ואילו ההוצאה בסיבוכיות $\ O(log\ n)$. זמנים אלו הם amortized. במימוש על ידי Strict Fibonacci heap, הזמנים יהיו במקרה הגרוע.

ישנם אלגוריתמים למימוש תור עדיפויות המאפשרים ביצוע כל הפעולות בסיבוכיות $\ O(log\ log\ n)$, ו$O({\sqrt {\log n}})$, אך הם מורכבים יותר, ודרישות הזיכרון שלהם לא מצדיקות לרוב שימוש בהם.

שימושים נפוצים

דוגמאות לשימוש במבנה הנתונים:

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

לקריאה נוספת

• Thomas H. Cormen, Charles E. Leiserson], Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. מסת"ב 0-262-03293-7. Section 6.5: Priority queues, pp. 138–142.

הערות שוליים

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

33590675תור עדיפויות