قائمة انتظار الأولوية هي نوع بيانات مجردة يتصرف بشكل مشابه لقائمة الانتظار العادية باستثناء أن كل عنصر له بعض الأولوية، أي أن العنصر ذو الأولوية العليا سيأتي أولاً في قائمة انتظار الأولوية. ستحدد أولوية العناصر الموجودة في قائمة انتظار الأولوية الترتيب الذي تتم به إزالة العناصر من قائمة انتظار الأولوية.
تدعم قائمة انتظار الأولوية العناصر القابلة للمقارنة فقط، مما يعني أن العناصر مرتبة إما بترتيب تصاعدي أو تنازلي.
ملفات لينكس
على سبيل المثال، لنفترض أن لدينا بعض القيم مثل 1، 3، 4، 8، 14، 22 مدرجة في قائمة انتظار الأولوية مع ترتيب مفروض على القيم من الأصغر إلى الأكبر. لذلك، سيكون للرقم 1 الأولوية القصوى بينما سيكون للرقم 22 الأولوية الأدنى.
خصائص قائمة الانتظار ذات الأولوية
قائمة الانتظار ذات الأولوية هي امتداد لقائمة انتظار تحتوي على الخصائص التالية:
- كل عنصر في قائمة انتظار الأولوية له بعض الأولوية المرتبطة به.
- سيتم حذف العنصر ذو الأولوية الأعلى قبل حذف الأولوية الأقل.
- إذا كان هناك عنصران في قائمة انتظار الأولوية لهما نفس الأولوية، فسيتم ترتيبهما باستخدام مبدأ FIFO.
دعونا نفهم قائمة انتظار الأولوية من خلال مثال.
لدينا قائمة انتظار ذات أولوية تحتوي على القيم التالية:
1، 3، 4، 8، 14، 22
يتم ترتيب جميع القيم بترتيب تصاعدي. الآن، سوف نلاحظ كيف سيكون شكل قائمة الانتظار ذات الأولوية بعد إجراء العمليات التالية:
أنواع قائمة الانتظار ذات الأولوية
هناك نوعان من قائمة الانتظار ذات الأولوية:
تمثيل قائمة الانتظار ذات الأولوية
الآن، سوف نرى كيفية تمثيل قائمة الانتظار ذات الأولوية من خلال قائمة ذات اتجاه واحد.
سنقوم بإنشاء قائمة انتظار الأولوية باستخدام القائمة الواردة أدناه معلومات تحتوي القائمة على عناصر البيانات، PRN تحتوي القائمة على أرقام الأولوية لكل عنصر بيانات متوفر في معلومات القائمة، وLINK يحتوي بشكل أساسي على عنوان العقدة التالية.
لنقم بإنشاء قائمة انتظار الأولوية خطوة بخطوة.
tostring java
في حالة قائمة الانتظار ذات الأولوية، يعتبر رقم الأولوية الأدنى هو الأولوية العليا، أي، رقم الأولوية الأدنى = الأولوية الأعلى.
الخطوة 1: في القائمة، رقم الأولوية الأدنى هو 1، وقيمة بياناته هي 333، لذلك سيتم إدراجه في القائمة كما هو موضح في الرسم البياني أدناه:
الخطوة 2: بعد إدراج 333، الأولوية رقم 2 لها أولوية أعلى، وقيم البيانات المرتبطة بهذه الأولوية هي 222 و111. لذا، سيتم إدراج هذه البيانات بناءً على مبدأ FIFO؛ لذلك سيتم إضافة 222 أولا ثم 111.
الخطوه 3: بعد إدراج عناصر الأولوية 2، يكون رقم الأولوية الأعلى التالي هو 4 وعناصر البيانات المرتبطة بأربعة أرقام أولوية هي 444، 555، 777. في هذه الحالة، سيتم إدراج العناصر بناءً على مبدأ FIFO؛ لذلك سيتم إضافة 444 أولاً، ثم 555، ثم 777.
الخطوة 4: بعد إدراج عناصر الأولوية 4، فإن رقم الأولوية الأعلى التالي هو 5، والقيمة المرتبطة بالأولوية 5 هي 666، لذلك سيتم إدراجها في نهاية قائمة الانتظار.
تنفيذ قائمة الانتظار ذات الأولوية
يمكن تنفيذ قائمة الانتظار ذات الأولوية بأربع طرق تتضمن المصفوفات والقائمة المرتبطة وبنية بيانات الكومة وشجرة البحث الثنائية. تعد بنية بيانات الكومة هي الطريقة الأكثر فعالية لتنفيذ قائمة الانتظار ذات الأولوية، لذلك سنقوم بتنفيذ قائمة الانتظار ذات الأولوية باستخدام بنية بيانات الكومة في هذا الموضوع. الآن، أولاً نفهم السبب الذي يجعل الكومة هي الطريقة الأكثر فعالية بين جميع هياكل البيانات الأخرى.
تحليل التعقيدات باستخدام تطبيقات مختلفة
| تطبيق | يضيف | يزيل | نظرة خاطفة |
| قائمة مرتبطة | يا(1) | على) | على) |
| كومة ثنائية | يا (تسجيل الدخول) | يا (تسجيل الدخول) | يا(1) |
| شجرة البحث الثنائية | يا (تسجيل الدخول) | يا (تسجيل الدخول) | يا(1) |
ما هو الكومة؟
الكومة عبارة عن بنية بيانات قائمة على الشجرة تشكل شجرة ثنائية كاملة وتفي بخاصية الكومة. إذا كانت A هي العقدة الأصلية للعقدة B، فسيتم ترتيب A فيما يتعلق بالعقدة B لجميع العقدتين A وB في الكومة. وهذا يعني أن قيمة العقدة الأصلية يمكن أن تكون أكبر من أو تساوي قيمة العقدة الفرعية، أو أن قيمة العقدة الأصلية يمكن أن تكون أقل من أو تساوي قيمة العقدة الفرعية. ولذلك يمكننا القول أن هناك نوعين من الأكوام:
charat java
كلا الكومة هي الكومة الثنائية، حيث تحتوي كل منها على عقدتين تابعتين بالضبط.
عمليات قائمة الانتظار ذات الأولوية
العمليات الشائعة التي يمكننا تنفيذها في قائمة انتظار الأولوية هي الإدراج والحذف والنظرة الخاطفة. دعونا نرى كيف يمكننا الحفاظ على بنية بيانات الكومة.
إذا قمنا بإدراج عنصر في قائمة انتظار الأولوية، فسوف ينتقل إلى الفتحة الفارغة من خلال النظر من الأعلى إلى الأسفل ومن اليسار إلى اليمين.
إذا لم يكن العنصر في مكانه الصحيح، فسيتم مقارنته بالعقدة الأصلية؛ إذا تم اكتشافه خارج الترتيب، يتم تبديل العناصر. تستمر هذه العملية حتى يتم وضع العنصر في الموضع الصحيح.
كما نعلم أنه في الكومة القصوى، فإن الحد الأقصى للعنصر هو العقدة الجذرية. عندما نقوم بإزالة العقدة الجذرية، فإنها تخلق فتحة فارغة. ستتم إضافة العنصر الأخير المدرج في هذه الفتحة الفارغة. بعد ذلك، تتم مقارنة هذا العنصر مع العقد الفرعية، أي الطفل الأيسر والطفل الأيمن، ويتم مبادلة مع الأصغر من الاثنين. ويستمر في التحرك إلى أسفل الشجرة حتى تتم استعادة خاصية الكومة.
تطبيقات قائمة الانتظار ذات الأولوية
فيما يلي تطبيقات قائمة انتظار الأولوية:
- يتم استخدامه في خوارزمية Dijkstra للمسار الأقصر.
- يتم استخدامه في خوارزمية Prim
- يتم استخدامه في تقنيات ضغط البيانات مثل كود هوفمان.
- يتم استخدامه في فرز الكومة.
- يتم استخدامه أيضًا في أنظمة التشغيل مثل جدولة الأولويات وموازنة التحميل ومعالجة المقاطعات.
برنامج لإنشاء قائمة انتظار الأولوية باستخدام الكومة الثنائية القصوى.
#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])>