تحليل رمز المصدر واستخدام هيكل قائمة انتظار الأولوية الأولوية في جافا

1. بنية البيانات ذات الأولوية

بنية بيانات الأولوية (قائمة انتظار الأولوية) في JDK7 هي كومة ثنائية. أن تكون دقيقًا ، إنها أصغر كومة.

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

رأس الفريق الأولوية هو أصغر عنصر بالترتيب المحدد.

لا يسمح PriorityQueue بقيم فارغة ولا يدعم كائنات غير قابلة للشفاء. يتطلب PriorityQueue استخدام واجهات قابلة للمقارنة ومقارنة لفرز الكائنات ، وسيتم معالجة العناصر الموجودة فيها وفقًا للأولوية عند الفرز.

حجم الأولوية غير محدود ، ولكن يمكن تحديد الحجم الأولي عند إنشائها. عند إضافة عناصر قائمة الانتظار ، سيتم توسيع قائمة الانتظار تلقائيًا.

PriorityQueue ليس آمنًا لخيط الخيط ، فالأولوية المماثلة هي آمنة مؤشرات الترابط.

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

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

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

حجم قائمة انتظار الأولوية غير مقيد ، ولكن يمكن تحديد الحجم الأولي في وقت الإنشاء. عندما نضيف عناصر إلى قائمة انتظار الأولوية ، سيزداد حجم قائمة الانتظار تلقائيًا.

PriorityQueue غير آمن ، لذلك توفر Java priorityblockingqueue (تنفيذ واجهة blockingqueue) لبيئات Java متعددة الخيوط.

2. تحليل رمز المصدر الأولوية

عضو:

 priavte كائن عابر [] قائمة انتظار ؛ حجم int الخاص = 0 ؛

1. عملية بناء كومة قمة صغيرة من قبل الأولوية

نستخدم هنا مُنشئ الأولوية لتمرير حاوية كأولوية المعلمة (collecntion <؟ تمتد e> مثال:

تنقسم عملية بناء كومة صغيرة صغيرة تقريبًا إلى خطوتين:

نسخ بيانات الحاوية وتحقق مما إذا كانت بيانات الحاوية خالية

 private void inselementsfromCollection (collection <؟ extends e> c) {object [] a = c.toarray () ؛ // إذا كان C.Tooraray لا يرجع بشكل غير صحيح الكائن [] ، فقم بنسخه. if (a.getClass ()! = object []. class) a = arrays.copyof (a ، a.length ، object []. class) ؛ int len ​​= A.Length ؛ if (len == 1 || this.comparator! = null) لـ (int i = 0 ؛ i <len ؛ i ++) if (a [i] == null) رمي nullpointerxception () ؛ this.queue = a ؛ this.size = A.Length ؛}

اضبط لجعل البيانات تلبي بنية الكومة العلوية الصغيرة.
أولاً ، طريقتان للتكيف: Siftup و Siftdown

SIFTDown: عند إعطاء عنصر تهيئة ، يجب تعديل العنصر بحيث يفي بالخصائص الهيكلية للحد الأدنى من الكومة. لذلك ، تتم مقارنة القيمة الرئيسية للعنصر X باستمرار وتبادلها مع الطفل من أعلى إلى أسفل حتى يتم العثور على أن القيمة الرئيسية للعنصر X أقل من أو تساوي القيمة الرئيسية للطفل (أي ، من الضمان أن تكون أصغر من قيم العقدة اليسرى واليمنى) ، أو تسقط مع العقدة الورقية.
على سبيل المثال ، كما هو موضح في الرسم البياني التالي ، اضبط هذه العقدة 9:

 private void siftDownComparable (int k ، e x) {قابلة للمقارنة <؟ super e> key = (قابلة للمقارنة <؟ super e>) x ؛ int half = size >>> 1 ؛ // size/2 هو تراكب للعقدة الورقية الأولى // طالما لم يتم الوصول إلى عقدة الورقة بينما (k <half) {int child = (k << 1) + 1 ؛ // غادر الطفل الكائن C = قائمة الانتظار [الطفل] ؛ int اليمين = الطفل + 1 ؛ // اكتشف أصغر وأصغر الأطفال من الأطفال الأيسر واليمين (يمين <الحجم && ((قابلة للمقارنة <؟ super e>) c) .Compareto ((e) قائمة الانتظار [يمين])> 0) c = Queue [child = right] ؛ if (key.compareto ((e) c) <= 0) break ؛ قائمة الانتظار [k] = c ؛ ك = طفل ؛ } قائمة الانتظار [k] = المفتاح ؛}

SIFTUP: يقوم PriorityQueue بإدراج العنصر الجديد في الذيل في كل مرة يتم فيها إضافة عنصر جديد. لذلك ، يجب أن يكون هناك نفس عملية التعديل مثل Siftdown ، باستثناء التكيف من أسفل (الورقة) لأعلى.
على سبيل المثال ، املأ العقدة بالمفتاح 3 في الرسم البياني التالي:

 private void siftupComparable (int k ، e x) {قابلة للمقارنة <؟ super e> key = (قابلة للمقارنة <؟ super e>) x ؛ بينما (k> 0) {int parent = (k - 1) >>> 1 ؛ // الحصول على كائن الوالد المشترك e = قائمة الانتظار [الأصل] ؛ if (key.compareto ((e) e)> = 0) break ؛ قائمة الانتظار [k] = e ؛ ك = الوالدين ؛ } قائمة الانتظار [k] = المفتاح ؛}

العملية الكلية لبناء كومة صغيرة هي:

 private void initFromCollection (مجموعة <؟ تمتد e> c) {initElementsFromCollection (c) ؛ ثقيل()؛ }

من بينها ، Heapify هي عملية Siftdown.

2. عملية توسيع سعة الأولوية

كما يتضح من أعضاء المثيل ، تحتفظ PriorityQueue كائن [] ، وبالتالي فإن طريقة التوسع الخاصة بها تشبه قائمة ArrayList.
يتم تقديم رمز المصدر فقط لطريقة النمو هنا

 Private void تنمو (int mincapacity) {int oldcapacity = queue.length ؛ // حجم مزدوج إذا كانت صغيرة ؛ آخر ينمو بنسبة 50 ٪ int newCapacity = OldCapacity + ((OldCapacity <64)؟ (OldCapacity + 2): (OldCapacity >> 1)) ؛ // الكود المتفوق في التدفق إذا (newCapacity - max_array_size> 0) newCapacity = hugecapacity (minicapacity) ؛ Queue = arrays.copyof (قائمة الانتظار ، newCapacity) ؛ }

يمكن ملاحظة أنه عندما تكون قدرة الصفيف كبيرة ، فإن السعة ليست كبيرة في كل مرة. عندما تكون سعة الصفيف أكبر من 64 ، يتم توسيع مزدوج في كل مرة.

3. تطبيق الأولوية

EG1:
فيما يلي أبسط تطبيق: ابحث عن رقم K-Th أكبر من البيانات الديناميكية.
الفكرة هي الحفاظ على كومة قمة صغيرة مع حجم = ك.

 // البيانات عبارة عن بيانات ديناميكية // الكومة تحافظ على بيانات ديناميكية // res تستخدم لحفظ Kthlarest boolean kthlarest (بيانات int ، int k ، priorityqueue <integer> ، int [] res) {if (heap.size () <k) if (heap.size () == k) {res [0] = heap.peek () ؛ العودة صحيح. } إرجاع خطأ ؛ } if (Heap.Peek () <data) {heap.poll () ؛ Heap.Offer (البيانات) ؛ } res [0] = heap.peek () ؛ العودة صحيح. }

EG2:
لدينا عميل فئة مستخدم لا يوفر أي نوع من النوع. عندما نستخدمه لإنشاء قائمة انتظار ذات أولوية ، يجب أن نوفرها كائن المقارنة.

customer.java

 حزمة com.journaldev.collections ؛ عميل الطبقة العامة {private int id ؛ اسم السلسلة الخاصة ؛ العميل العام (int i ، string n) {this.id = i ؛ this.name = n ؛ } public int getId () {return id ؛ } السلسلة العامة getName () {return name ؛ }}

نستخدم أرقام Java العشوائية لإنشاء كائنات مستخدم عشوائية. للفرز الطبيعي ، نستخدم كائن عدد صحيح ، وهو أيضًا كائن Java مغلف.
فيما يلي رمز الاختبار النهائي الذي يوضح كيفية استخدام PriorityQueue:

phiretityequeexample.java

 حزمة com.journaldev.collections ؛ استيراد java.util.comparator ؛ استيراد java.util.priorityqueue ؛ استيراد java.util.queue ؛ استيراد java.util.random ؛ الفئة العامة priorityequeexample {public static void main (string [] args) {// قائمة قائمة الانتظار الطبيعية ذات الأولوية ، قائمة قائمة الانتظار الطبيعية <integer> integerPriorityQueue = new PriorityQueue <> (7) ؛ Rand Rand = New Random () ؛ لـ (int i = 0 ؛ i <7 ؛ i ++) {integerpriorityqueue.add (integer new (rand.nextint (100))) ؛ } لـ (int i = 0 ؛ i <7 ؛ i ++) {integer in = integerpriorityqueue.poll () ؛ System.out.println ("معالجة عدد صحيح:"+in) ؛ }. addDataTequeue (customerpriorityqueue) ؛ polldatafromqueue (customerpriorityqueue) ؛ }. }} ؛ // الطريقة العالمية المستخدمة لإضافة بيانات إلى قائمة الانتظار private adddatatoqueue (قائمة الانتظار <suntern> customerpriorityqueue) {Random Rand = new Random () ؛ لـ (int i = 0 ؛ i <7 ؛ i ++) {int id = rand.nextint (100) ؛ customerpriorityqueue.add (عميل جديد (معرف ، "pankaj"+id)) ؛ }} // الطريقة العامة لجلب البيانات من قائمة انتظار proldatafromqueue static proldatafromque (قائمة الانتظار <Puonner> customerpriorityqueue) {بينما (صحيح) {customer cust = customerpriorityue.poll () ؛ إذا (CUST == NULL) استراحة ؛ system.out.println ("معالجة العميل مع id ="+cust.getID ()) ؛ }}}}

لاحظ أنني أستخدم فئة Java Anonymous التي تنفذ واجهة المقارنة وتنفذ مقارنة قائمة على الهوية.
عندما أقوم بتشغيل برنامج الاختبار أعلاه ، أحصل على الإخراج التالي:

 المعالجة عدد صحيح: 9PROSESTING INTEGER: عدد صحيح 1600: 18PROSISTING INTEGER: 25Processing INTEGER: 33PROCESS INTEGER: 75PPROCESS INTEGER: 77PROCESSE مع العميل = 29PROCESS المعرف = 82Processing عميل مع معرف = 96

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

 استثناء في الموضوع "Main" java.lang.classcastexception: com.journaldev.collections.customer لا يمكن إلقاؤه إلى java.lang.comparable على java.util.priorityqueue.siftupComparable (priorityequue.java:633) على java.util.priority.siftup java.util.priorityqueue.offer (phiretiqueue.java:329) في java.util.priorityqueue.add (phiretiqueue.java:306) في com.journaldev.collections.prioritequeexample com.journaldev.collections.priorityqueueexample.main (phiretiqueeexample.java:25)