תור עדיפויות

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

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

priority_queue<dataType> queueName

ראשית, עלינו לכלול את קובץ הכותרת של תור העדיפויות בראש קובץ ה-C++ שלנו. 

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

priority_queue<int> integers;

לאחר מכן, משתמשים בשיטה push() כדי להוסיף איברים חדשים לתור. האיבר נוסף, ואם הוא גדול יותר מכל האיברים, הוא יאוחסן ראשון. אם הוא קטן יותר מכל שאר האיברים, הוא יאוחסן אחרון, וכן הלאה.

integers.push(5);  // integers = {5)

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

integers.push(100);  // integers = {100, 5}
integers.push(10);  // integers = {100, 10, 5}
integers.push(3);  // integers = {100, 10, 5, 3}
cout << integers.top();

Output:
100

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

integers.pop();  // integers = {10, 5, 3}
cout << integers.top();

Output:
10

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

priority_queue<int, vector<int>, greater<int> > integers;

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

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

שיטות של תור עדיפויות