תור עדיפויות

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


תור עדיפויות תומך במספר פעולות הקשורות להוספה והסרה של פריטים. פירוט הפעולות והיעילות שלהן תלויים במימוש שבוחרים.

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


הסיבוכיות של פעולות בתור עדיפויות תלויה במימוש. הבחירה במימוש נעשית לפי צרכי המערכת. קיימים מימושים מתקדמים שמאפשרים סיבוכיות כמו O(log log n) ו‑O(√(log n)), אך הם מורכבים ודורשים זיכרון רב, ולכן אינם בשימוש נפוץ.


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

תור עדיפויות הוא דרך לסדר פריטים לפי חשיבות. 'עדיפות' אומרת כמה דבר חשוב.

תור רגיל יוצא לפי סדר הכניסה. זה נקרא FIFO (הכניסה הראשונה יוצאת ראשונה).


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

תור רגיל ומחסנית הם דוגמאות פשוטות. מחסנית (stack) היא מקום שבו בדרך כלל יוצא האחרון שנכנס.


המהירות והזיכרון שתור כזה צריך תלוים איך מיישמים אותו. יש שיטות מאוד מתקדמות, אבל הן מסובכות ודורשות הרבה זיכרון.


תור כזה שימושי כשצריך לקחת תמיד את מה שהכי חשוב קודם.