תור עדיפות הוא סוג נתונים מופשט שמתנהג באופן דומה לתור הרגיל, אלא שלכל אלמנט יש עדיפות מסוימת, כלומר, האלמנט בעל העדיפות הגבוהה ביותר יבוא ראשון בתור עדיפות. העדיפות של האלמנטים בתור עדיפות תקבע את סדר הסרת האלמנטים מתור העדיפות.
תור העדיפות תומך רק באלמנטים דומים, מה שאומר שהאלמנטים מסודרים בסדר עולה או יורד.
ההבדל בין נמר לאריה
לדוגמה, נניח שיש לנו כמה ערכים כמו 1, 3, 4, 8, 14, 22 מוכנסים בתור עדיפות עם סדר שהוטל על הערכים הוא מהפחות לגדול ביותר. לכן, המספר 1 יהיה בעל העדיפות הגבוהה ביותר בעוד ש-22 יהיה בעל העדיפות הנמוכה ביותר.
מאפיינים של תור פריוריטי
תור עדיפות הוא הרחבה של תור שמכיל את המאפיינים הבאים:
- לכל רכיב בתור עדיפות יש עדיפות מסוימת הקשורה אליו.
- אלמנט בעל עדיפות גבוהה יותר יימחק לפני מחיקת העדיפות הפחותה.
- אם לשני אלמנטים בתור עדיפות יש אותה עדיפות, הם יסודרו באמצעות עקרון ה-FIFO.
בואו נבין את תור העדיפות באמצעות דוגמה.
יש לנו תור עדיפות שמכיל את הערכים הבאים:
1, 3, 4, 8, 14, 22
כל הערכים מסודרים בסדר עולה. כעת, נראה כיצד יראה תור העדיפות לאחר ביצוע הפעולות הבאות:
סוגי תור עדיפות
ישנם שני סוגים של תור עדיפות:
ייצוג תור עדיפות
כעת, נראה כיצד לייצג את תור העדיפות באמצעות רשימה חד כיוונית.
אנו ניצור את תור העדיפות באמצעות הרשימה המופיעה להלן שבה מידע רשימה מכילה את רכיבי הנתונים, PRN רשימה מכילה את מספרי העדיפות של כל רכיב נתונים זמין ב- מידע list, ו-LINK מכיל בעצם את הכתובת של הצומת הבא.
בואו ניצור את תור העדיפות צעד אחר צעד.
tostring java
במקרה של תור עדיפות, מספר בעדיפות נמוכה יותר נחשב בעדיפות הגבוהה יותר, כלומר, מספר בעדיפות נמוכה = עדיפות גבוהה יותר.
שלב 1: ברשימה, המספר בעדיפות נמוכה יותר הוא 1, שערך הנתונים שלו הוא 333, ולכן הוא יוכנס לרשימה כפי שמוצג בתרשים שלהלן:
שלב 2: לאחר הוספת 333, עדיפות מספר 2 נמצאת בעדיפות גבוהה יותר, וערכי הנתונים המשויכים לעדיפות זו הם 222 ו-111. לכן, נתונים אלה יוכנסו בהתבסס על עקרון ה-FIFO; לכן 222 יתווספו תחילה ואז 111.
שלב 3: לאחר הוספת הרכיבים של עדיפות 2, המספר הבא בעדיפות גבוהה יותר הוא 4 ורכיבי נתונים המשויכים ל-4 מספרי עדיפות הם 444, 555, 777. במקרה זה, אלמנטים יוכנסו על בסיס עקרון ה-FIFO; לכן, תחילה יתווסף 444, לאחר מכן 555 ולאחר מכן 777.
שלב 4: לאחר הוספת הרכיבים של עדיפות 4, המספר הבא בעדיפות גבוהה יותר הוא 5, והערך המשויך לעדיפות 5 הוא 666, כך שהוא יוכנס בסוף התור.
יישום של תור עדיפות
ניתן ליישם את תור העדיפות בארבע דרכים הכוללות מערכים, רשימה מקושרת, מבנה נתונים ערימה ועץ חיפוש בינארי. מבנה הנתונים הערימה הוא הדרך היעילה ביותר ליישום תור העדיפות, לכן ניישם את תור העדיפות באמצעות מבנה נתונים ערימה בנושא זה. כעת, ראשית אנו מבינים את הסיבה מדוע heap היא הדרך היעילה ביותר מבין כל מבני הנתונים האחרים.
ניתוח של מורכבויות באמצעות יישומים שונים
| יישום | לְהוֹסִיף | לְהַסִיר | לְהָצִיץ |
| רשימה מקושרת | O(1) | עַל) | עַל) |
| ערימה בינארית | O(לוגן) | O(לוגן) | O(1) |
| עץ חיפוש בינארי | O(לוגן) | O(לוגן) | O(1) |
מה זה Heap?
ערמה היא מבנה נתונים מבוסס עץ היוצר עץ בינארי שלם, ומספק את תכונת הערימה. אם A הוא צומת אב של B, אז A מסודר ביחס לצומת B עבור כל הצמתים A ו-B בערימה. זה אומר שהערך של צומת האב יכול להיות יותר או שווה לערך של צומת הצאצא, או שהערך של צומת האב יכול להיות קטן או שווה לערך של צומת הצאצא. לכן, אנו יכולים לומר שיש שני סוגים של ערימות:
כיצד לקרוא קובץ json
שתי הערימות הן הערימה הבינארית, מכיוון שלכל אחת יש בדיוק שני צמתים צאצאים.
פעולות תור עדיפות
הפעולות הנפוצות שאנו יכולים לבצע בתור עדיפות הן הכנסה, מחיקה והצצה. בואו נראה כיצד נוכל לשמור על מבנה הנתונים הערימה.
אם נכניס אלמנט לתור עדיפות, הוא יעבור למשבצת הריקה על ידי הסתכלות מלמעלה למטה ומשמאל לימין.
אם האלמנט לא נמצא במקום הנכון, הוא מושווה לצומת האב; אם הוא נמצא לא תקין, אלמנטים מוחלפים. תהליך זה נמשך עד להצבת האלמנט במיקום הנכון.
כפי שאנו יודעים שבערמה מקסימלית, האלמנט המקסימלי הוא צומת השורש. כאשר אנו מסירים את צומת השורש, הוא יוצר חריץ ריק. הרכיב האחרון שהוכנס יתווסף למשבצת הריקה הזו. לאחר מכן, אלמנט זה מושווה עם צמתי הילד, כלומר, ילד שמאל וילד ימני, ומחליף עם הקטן מבין השניים. הוא ממשיך לנוע במורד העץ עד שרכוש הערימה משוחזר.
יישומים של תור עדיפות
להלן היישומים של תור העדיפות:
- הוא משמש באלגוריתם הנתיב הקצר ביותר של דיקסטרה.
- הוא משמש באלגוריתם של prim
- הוא משמש בטכניקות דחיסת נתונים כמו קוד Huffman.
- הוא משמש במיון ערימה.
- הוא משמש גם במערכת הפעלה כמו תזמון עדיפות, איזון עומסים וטיפול בפסיקות.
תוכנית ליצירת תור העדיפות באמצעות ערימת המקסימום הבינארית.
#include #include int heap[40]; int size=-1; // retrieving the parent node of the child node int parent(int i) { return (i - 1) / 2; } // retrieving the left child of the parent node. int left_child(int i) { return i+1; } // retrieving the right child of the parent int right_child(int i) { return i+2; } // Returning the element having the highest priority int get_Max() { return heap[0]; } //Returning the element having the minimum priority int get_Min() { return heap[size]; } // function to move the node up the tree in order to restore the heap property. void moveUp(int i) { while (i > 0) { // swapping parent node with a child node if(heap[parent(i)] <heap[i]) 2 { int temp; temp="heap[parent(i)];" heap[parent(i)]="heap[i];" heap[i]="temp;" } updating the value of i to function move node down tree in order restore heap property. void movedown(int k) index="k;" getting location left child if (left heap[index]) right (right k is not equal (k !="index)" heap[index]="heap[k];" heap[k]="temp;" movedown(index); removing element maximum priority removemax() r="heap[0];" heap[0]="heap[size];" size="size-1;" movedown(0); inserting a queue insert(int p) + 1; heap[size]="p;" up maintain property moveup(size); from at given i. delete(int i) stored ith shifted root moveup(i); having removemax(); main() elements insert(20); insert(19); insert(21); insert(18); insert(12); insert(17); insert(15); insert(16); insert(14); printf('elements are : '); for(int printf('%d ',heap[i]); delete(2); deleting whose 2. printf('
elements after max="get_Max();" printf('
the which highest %d: ',max); min="get_Min();" minimum %d',min); return 0; < pre> <p> <strong>In the above program, we have created the following functions:</strong> </p> <ul> <tr><td>int parent(int i):</td> This function returns the index of the parent node of a child node, i.e., i. </tr><tr><td>int left_child(int i):</td> This function returns the index of the left child of a given index, i.e., i. </tr><tr><td>int right_child(int i):</td> This function returns the index of the right child of a given index, i.e., i. </tr><tr><td>void moveUp(int i):</td> This function will keep moving the node up the tree until the heap property is restored. </tr><tr><td>void moveDown(int i):</td> This function will keep moving the node down the tree until the heap property is restored. </tr><tr><td>void removeMax():</td> This function removes the element which is having the highest priority. </tr><tr><td>void insert(int p):</td> It inserts the element in a priority queue which is passed as an argument in a function <strong>.</strong> </tr><tr><td>void delete(int i):</td> It deletes the element from a priority queue at a given index. </tr><tr><td>int get_Max():</td> It returns the element which is having the highest priority, and we know that in max heap, the root node contains the element which has the largest value, and highest priority. </tr><tr><td>int get_Min():</td> It returns the element which is having the minimum priority, and we know that in max heap, the last node contains the element which has the smallest value, and lowest priority. </tr></ul> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/what-is-priority-queue-9.webp" alt="Priority Queue"> <hr></heap[i])>