قائمة انتظار الأولوية في بنية البيانات: الخصائص والأنواع والتنفيذ

نشرت: 2021-05-02

جدول المحتويات

مقدمة

قائمة انتظار الأولوية في بنية البيانات هي امتداد لقائمة الانتظار "العادية". إنه نوع بيانات مجردة يحتوي على مجموعة من العناصر. إنها مثل قائمة الانتظار "العادية" فيما عدا أن عناصر إلغاء الترتيب تتبع ترتيب أولوية. يقوم ترتيب الأولوية بإلغاء ترتيب العناصر التي لها الأولوية القصوى أولاً. ستمنحك هذه المدونة فهمًا أعمق لقائمة الانتظار ذات الأولوية وتنفيذها بلغة البرمجة سي.

ما هي أولوية قائمة الانتظار؟

إنه نوع بيانات مجردة يوفر طريقة للحفاظ على مجموعة البيانات. قائمة الانتظار "العادية" تتبع نمط الوارد أولاً يصرف أولاً. يقوم بفصل العناصر من نفس الترتيب المتبع في وقت عملية الإدراج. ومع ذلك ، فإن ترتيب العنصر في قائمة انتظار الأولوية يعتمد على أولوية العنصر في قائمة الانتظار تلك. تقوم قائمة انتظار الأولوية بنقل العناصر ذات الأولوية القصوى في بداية قائمة انتظار الأولوية والعناصر الأقل أولوية في الجزء الخلفي من قائمة انتظار الأولوية.

إنه يدعم فقط تلك العناصر القابلة للمقارنة. ومن ثم ، فإن قائمة انتظار الأولوية في بنية البيانات ترتب العناصر إما بترتيب تصاعدي أو تنازلي.

يمكنك التفكير في قائمة انتظار ذات أولوية لأن العديد من المرضى ينتظرون في طابور في المستشفى. هنا ، تحدد حالة المريض ترتيب الأولوية. سيكون المريض المصاب بأشد الإصابات هو الأول في قائمة الانتظار.

ما هي خصائص قائمة انتظار الأولوية؟

يُطلق على قائمة الانتظار على أنها قائمة انتظار ذات أولوية إذا كانت تحتوي على الخصائص التالية:

  • كل عنصر له بعض الأولوية المرتبطة به.
  • يتم نقل العنصر ذي الأولوية القصوى في المقدمة وحذفه أولاً.
  • إذا كان هناك عنصران يشتركان في نفس قيمة الأولوية ، فإن قائمة انتظار الأولوية تتبع مبدأ الوارد أولاً يخرج أولاً لعملية de queue.

ما هي أنواع الأولوية في قائمة الانتظار؟

قائمة انتظار الأولوية من نوعين:

  • ترتيب أولوية ترتيب تصاعدي
  • ترتيب ترتيب الأولوية قائمة انتظار

ترتيب أولوية ترتيب تصاعدي

تعطي قائمة انتظار أولوية الترتيب التصاعدي الأولوية القصوى للرقم الأقل في قائمة الانتظار تلك. على سبيل المثال ، لديك ستة أرقام في قائمة انتظار الأولوية وهي 4 ، 8 ، 12 ، 45 ، 35 ، 20. أولاً ، ستقوم بترتيب هذه الأرقام بترتيب تصاعدي. القائمة الجديدة هي كما يلي: 4 ، 8 ، 12 ، 20. 35 ، 45. في هذه القائمة ، 4 هو أصغر رقم. ومن ثم ، فإن قائمة انتظار أولوية الترتيب التصاعدي تتعامل مع الرقم 4 كأولوية قصوى.

4 8 12 20 35 45

في الجدول أعلاه ، 4 لها الأولوية القصوى ، و 45 لها الأولوية الدنيا.

ترتيب ترتيب الأولوية قائمة انتظار

تعطي قائمة انتظار الأولوية بالترتيب التنازلي الأولوية القصوى لأعلى رقم في قائمة الانتظار تلك. على سبيل المثال ، لديك ستة أرقام في قائمة انتظار الأولوية وهي 4 ، 8 ، 12 ، 45 ، 35 ، 20. أولاً ، ستقوم بترتيب هذه الأرقام بترتيب تصاعدي. القائمة الجديدة هي كما يلي: 45 ، 35 ، 20 ، 12 ، 8 ، 4. في هذه القائمة ، 45 هو الرقم الأعلى. ومن ثم ، فإن قائمة انتظار أولوية الترتيب التنازلي تتعامل مع الرقم 45 كأولوية قصوى.

45 35 20 12 8 4

في الجدول أعلاه ، 4 لها أقل أولوية ، و 45 لها أولوية قصوى.

تنفيذ قائمة انتظار الأولوية في بنية البيانات

يمكنك تنفيذ قوائم الانتظار ذات الأولوية بإحدى الطرق التالية:

  • قائمة مرتبطة
  • كومة ثنائية
  • المصفوفات
  • شجرة بحث ثنائية

الكومة الثنائية هي الطريقة الأكثر فعالية لتنفيذ قائمة انتظار الأولوية في بنية البيانات .

تلخص الجداول أدناه مدى تعقيد العمليات المختلفة في قائمة انتظار الأولوية.

عملية مصفوفة غير مرتبة ترتيب متناسق كومة ثنائية شجرة البحث الثنائية
إدراج 0 (1) 0 (N) 0 (تسجيل (N)) 0 (تسجيل (N))
نظرة خاطفة 0 (N) 0 (1) 0 (1) 0 (1)
حذف 0 (N) 0 (1) 0 (تسجيل (N)) 0 (تسجيل (N))

كومة ثنائية

تنظم شجرة الكومة الثنائية جميع العقد الأصلية والفرعية للشجرة بترتيب معين. في شجرة كومة ثنائية ، يمكن أن تحتوي العقدة الأصلية على عقدتين فرعيتين بحد أقصى. يمكن أن تكون قيمة العقدة الأصلية:

  • يساوي أو أقل من قيمة العقدة الفرعية.
  • يساوي أو يزيد عن قيمة العقدة الفرعية.

تقسم العملية المذكورة أعلاه الكومة الثنائية إلى نوعين: max heap و min-heap.

ماكس كومة

الكومة القصوى هي كومة ثنائية تحتوي فيها العقدة الأصلية على قيمة مساوية لقيمة العقدة الفرعية أو أكبر منها. أعلى قيمة لعقدة جذر الشجرة.

إدراج عنصر في شجرة ثنائية كومة بحد أقصى

يمكنك تنفيذ الخطوات التالية لإدراج عنصر / رقم في قائمة انتظار الأولوية في بنية البيانات .

  1. تقوم الخوارزمية بمسح الشجرة من أعلى إلى أسفل ومن اليسار إلى اليمين للعثور على فتحة فارغة. ثم يقوم بإدراج العنصر في العقدة الأخيرة في الشجرة.
  2. بعد إدخال العنصر ، يتم إزعاج ترتيب الشجرة الثنائية. يجب عليك مبادلة البيانات مع بعضها البعض لفرز ترتيب الشجرة الثنائية القصوى لكومة الذاكرة المؤقتة. يجب أن تستمر في تبديل البيانات حتى تفي الشجرة بخاصية max-heap.

خوارزمية لإدراج عنصر في شجرة ثنائية كومة بحد أقصى

إذا كانت الشجرة فارغة ولا تحتوي على عقدة ،

إنشاء عقدة أصل جديدة newElement.

آخر (العقدة الرئيسية متاحة بالفعل)

أدخل العنصر الجديد في نهاية الشجرة (على سبيل المثال ، العقدة الأخيرة للشجرة من اليسار إلى اليمين.)

max-heapify الشجرة

حذف عنصر في شجرة ثنائية كومة بحد أقصى

  1. يمكنك تنفيذ الخطوات التالية لحذف عنصر في قائمة انتظار الأولوية في بنية البيانات .
  2. اختر العنصر الذي تريد حذفه من الشجرة الثنائية.
  3. قم بتحويل البيانات الموجودة في نهاية الشجرة عن طريق تبديلها ببيانات العقدة الأخيرة.
  4. قم بإزالة العنصر الأخير من الشجرة الثنائية.
  5. بعد حذف العنصر ، يتم إزعاج ترتيب الشجرة الثنائية. يجب عليك فرز الترتيب لتلبية خاصية max-heap. يجب أن تستمر في تبديل البيانات حتى تتوافق الشجرة مع خاصية max-heap.

خوارزمية لحذف عنصر في شجرة ثنائية كومة بحد أقصى

إذا كانت elementUpForDeletion هي lastNode ،

حذف عنصر UpForDeletion

وإلا استبدل elementUpForDeletion بالعقدة الأخيرة

حذف عنصر UpForDeletion

max-heapify الشجرة

ابحث عن الحد الأقصى أو الحد الأدنى للعنصر في شجرة ثنائية كومة قصوى

في الشجرة الثنائية القصوى لكومة الذاكرة المؤقتة ، تُرجع عملية البحث العقدة الأصلية (أعلى عنصر) للشجرة.

خوارزمية للعثور على الحد الأقصى أو الحد الأدنى في شجرة ثنائية كومة الحد الأقصى

إرجاع ParentNode

تنفيذ برنامج قائمة انتظار الأولوية باستخدام شجرة Max Heap الثنائية

# تضمين <stdio.h>

int binary_tree = 10 ؛

int max_heap = 0 ؛

اختبار const int = 100000 ؛

مبادلة باطلة (int * x، int * y) {

الباحث أ ؛

أ = * س ؛

* س = * ص ؛

* ص = أ ؛

}

// كود للعثور على الأصل في شجرة الكومة القصوى

int findParentNode (int node []، int root) {

إذا ((الجذر> 1) && (الجذر <binary_tree)) {

عودة الجذر / 2 ؛

}

عودة -1 ؛

}

max_heapify باطل (عقدة int [] ، جذر int) {

int leftNodeRoot = findLeftChild (عقدة ، جذر) ؛

int rightNodeRoot = findRightChild (عقدة ، جذر) ،

// إيجاد أعلى بين الجذر ، الطفل الأيسر والطفل الأيمن

int الأعلى = الجذر ؛

إذا ((leftNodeRoot <= max_heap) && (leftNodeRoot> 0)) {

إذا (العقدة [leftNodeRoot]> العقدة [الأعلى]) {

أعلى = leftNodeRoot ؛

}

}

إذا ((rightNodeRoot <= max_heap) && (rightNodeRoot> 0)) {

إذا (العقدة [rightNodeRoot]> العقدة [الأعلى]) {

أعلى = rightNodeRoot ؛

}

}

إذا (أعلى! = جذر) {

مبادلة (& عقدة [جذر] ، & عقدة [أعلى]) ؛

max_heapify (العقدة ، الأعلى) ؛

}

}

create_max_heap باطلة (عقدة int []) {

كثافة العمليات د ؛

لـ (d = max_heap / 2 ؛ d> = 1 ؛ d–) {

max_heapify (العقدة ، د) ؛

}

}

الحد الأقصى int (العقدة int []) {

عقدة العودة [1] ؛

}

int find_max (int node []) {

int maxNode = العقدة [1] ؛

العقدة [1] = العقدة [max_heap] ؛

max_heap– ؛

max_heapify (عقدة ، 1) ؛

عودة maxNode ؛

}

مفتاح descend_key باطل (عقدة int [] ، عقدة int ، مفتاح int) {

أ [جذر] = مفتاح ؛

max_heapify (عقدة ، جذر) ؛

}

مفتاح زيادة باطل (عقدة int [] ، جذر int ، مفتاح int) {

عقدة [جذر] = مفتاح ؛

while ((root> 1) && (node ​​[findParentNode (node، root)] <node [root])) {

swap (& node [root]، & node [findParentNode (node، root)]) ؛

الجذر = findParentNode (عقدة ، جذر) ؛

}

}

إدراج باطل (عقدة int [] ، مفتاح int) {

max_heap ++ ؛

العقدة [max_heap] = -1 * اختبار ؛

زيادة_المفتاح (عقدة ، max_heap ، مفتاح) ؛

}

display_heap باطل (عقدة int []) {

كثافة العمليات د ؛

لـ (d = 1 ؛ d <= max_heap ؛ d ++) {

printf ("٪ d \ n" ، العقدة [d]) ؛

}

printf ("\ n") ؛

}

انت مين() {

عقدة int [binary_tree] ؛

إدراج (عقدة ، 10) ؛

إدراج (عقدة ، 4) ؛

إدراج (عقدة ، 20) ؛

إدراج (عقدة ، 50) ؛

إدراج (عقدة ، 1) ؛

إدراج (عقدة ، 15) ؛

display_heap (عقدة) ؛

printf ("٪ d \ n \ n" ، الحد الأقصى (عقدة)) ؛

display_heap (عقدة) ؛

printf ("٪ d \ n"، extract_max (عقدة)) ؛

printf ("٪ d \ n"، extract_max (عقدة)) ؛

العودة 0 ؛

}

كومة دقيقة

min-heap هو كومة ثنائية تحتوي فيها العقدة الأصلية على قيمة مساوية لقيمة العقدة الفرعية أو أقل منها. أقل قيمة لعقدة جذر الشجرة.

يمكنك تطبيق min-heap بنفس الطريقة مثل max-heap باستثناء عكس الترتيب.

خاتمة

الأمثلة الواردة في المقالة هي لأغراض توضيحية فقط. يمكنك تعديل البيانات الواردة أعلاه وفقًا لمتطلباتك. في هذه المدونة ، تعرفنا على مفهوم قائمة الانتظار ذات الأولوية في بنية البيانات . يمكنك تجربة المثال لتقوية معرفتك بهيكل البيانات.

إذا كنت مهتمًا بالتعرف على علوم البيانات ، فراجع برنامج IIIT-B & upGrad التنفيذي PG في علوم البيانات الذي تم إنشاؤه للمهنيين العاملين ويقدم أكثر من 10 دراسات حالة ومشاريع ، وورش عمل عملية عملية ، وإرشاد مع خبراء الصناعة ، 1 - في 1 مع موجهين في الصناعة ، أكثر من 400 ساعة من التعلم والمساعدة في العمل مع الشركات الكبرى.

تعلم دورات علوم البيانات عبر الإنترنت من أفضل الجامعات في العالم. اربح برامج PG التنفيذية أو برامج الشهادات المتقدمة أو برامج الماجستير لتتبع حياتك المهنية بشكل سريع.

ما هي تطبيقات قائمة انتظار الأولوية؟

قائمة انتظار الأولوية هي قائمة انتظار خاصة حيث يتم إدراج العناصر على أساس أولويتها. تصبح هذه الميزة مفيدة في تنفيذ العديد من هياكل البيانات الأخرى. فيما يلي بعض التطبيقات الأكثر شيوعًا لقائمة انتظار الأولوية:
 1. خوارزمية Dijkstra's Shortest Path: يمكن استخدام قائمة انتظار الأولوية في خوارزمية أقصر مسار في Dijkstra عندما يتم تخزين الرسم البياني في شكل قائمة الجوار.
 2. خوارزمية Prim: تستخدم خوارزمية Prim قائمة انتظار الأولوية لقيم أو مفاتيح العقد وترسم الحد الأدنى من هذه القيم في كل خطوة.
 ضغط البيانات : تستخدم أكواد هوفمان قائمة انتظار الأولوية لضغط البيانات.
 أنظمة التشغيل: تعد قائمة انتظار الأولوية مفيدة للغاية لأنظمة التشغيل في عمليات مختلفة مثل موازنة الحمل ومعالجة الانقطاع.

ما هو النهج المستخدم في تنفيذ قائمة انتظار الأولوية باستخدام المصفوفة؟

الطريقة المستخدمة في تنفيذ قائمة انتظار الأولوية باستخدام مصفوفة بسيطة. يتم إنشاء هيكل لتخزين قيم وأولوية العنصر ثم يتم إنشاء مصفوفة تلك البنية لتخزين العناصر. يتم تضمين العمليات التالية في هذا التنفيذ:
 1. قائمة الانتظار () - تُدرج هذه الوظيفة العناصر في نهاية قائمة الانتظار.
 2. نظرة خاطفة () - ستجتاز هذه الوظيفة المصفوفة لإرجاع العنصر ذي الأولوية القصوى. إذا وجد عنصرين لهما نفس الأولوية ، فإنه يُرجع عنصر القيمة الأعلى بينهما.
 3. dequeue () - ستعمل هذه الوظيفة على نقل جميع العناصر ، وموضعًا واحدًا على يسار العنصر الذي تعيده وظيفة peek () وتقليل الحجم.

ما هو الفرق بين الحد الأقصى للكومة والصغرى؟

يوضح ما يلي الفرق بين أقصى كومة و min-heap.
 Min Heap - في min-heap ، يجب أن يكون مفتاح عقدة الجذر أقل من أو يساوي مفاتيح العقدة الفرعية الخاصة بها. يستخدم أولوية تصاعدية. العقدة ذات أصغر مفتاح هي الأولوية. يظهر أصغر عنصر قبل أي عنصر آخر.
 Max Heap - في الكومة القصوى ، يجب أن يكون مفتاح عقدة الجذر أكبر من أو يساوي مفتاح العقد التابعة لها. يستخدم أولوية تنازلية. العقدة ذات المفتاح الأكبر هي الأولوية. يظهر أكبر عنصر قبل أي عنصر آخر.