מדריך למתחילים להבנת תורים ותורי עדיפות

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

המשך לקרוא כדי להבין תורים ותורי עדיפות.

מהו תור?

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

מבחינת מורכבות הזמן, תור מאפשר הכנסה (אנקה) ומחיקה (התרוקנות) בזמן O (1). בשל היעילות האסימפטוטית, התורים יעילים למערכי נתונים גדולים. התורים באופיים ראשונים-ראשון-החוצה (FIFO), כלומר פריט נתונים שיוכנס תחילה ייכנס לראשונה. לעומת זאת, לערימות יש אופי אחרון-ראשון-החוצה (LIFO) ויש להן רק קצה אחד פתוח.

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

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

מהו תור עדיפות?

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

קָשׁוּר: אלגוריתמים שכל מתכנת צריך לדעת

מתכנתים יכולים ליישם תור עדיפות בכמה דרכים. יישום פשוט הוא שימוש במערך עם פריט נתונים struct/class, ופריט הנתונים יכיל את עדיפות כל רכיב נתונים והנתונים עצמם. יישום תור עדיפות פרימיטיבי נוסף הוא שימוש ברשימה מקושרת. תורי עדיפות המיושמים באמצעות רשימות מקושרות הם פונקציונליים אך אינם אידיאליים בשל הביצועים שלהם.

אתה יכול ליישם תור עדיפות טוב יותר עם ערימה. אם אתה זוכר, ערמות בינאריות נותנות את המרכיב המרבי או המינימלי תוך 0 (1) זמן, וההכנסה אורכת רק 0 (logN) זמן. בעזרת ערמות, תורי עדיפות נותנים ביצועים טובים יותר באופן אסימפטטי בהשוואה לתורים או מערכים.

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

למד מבני נתונים

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

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

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

ערמות מול ערימות: מה מייחד אותן?

שמעתם על ערמות וערימות, אבל מתי כדאי להשתמש בזה על פני השני?

קרא הבא

על הסופר