תור עדיפויות

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

פעולות על מבנה הנתונים[עריכת קוד מקור | עריכה]

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

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

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

ניתוח סיבוכיות[עריכת קוד מקור | עריכה]

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

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

שימושים נפוצים[עריכת קוד מקור | עריכה]

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

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

לקריאה נוספת[עריכת קוד מקור | עריכה]

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

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ P. van Emde Boas. Preserving order in a forest in less than logarithmic time. In Proceedings of the 16th Annual Symposium on Foundations of Computer Science, pages 75-84. IEEE Computer Society, 1975.
  2. ^ Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences, 48(3):533-551, 1994