ستمنحك هذه المقالة نظرة عامة كاملة على عمل فرز الكومة وبعد ذلك سنتعلم كيفية تنفيذ Binary Heap في Java.
هنا جدول أعمال هذا المقال:
- ما هو نوع الكومة؟
- ماكس كومة
- كومة دقيقة
- تنفيذ الكومة في Java
- رسم بياني
- الشفرة
هيا نبدأ!
ما هو نوع الكومة؟
الكومة هي أساسًا هيكل بيانات قائم على الأشجار. لديها عقد. تتكون العقدة من عناصر معينة. كل عقدة تحتوي على عنصر واحد.
قد يكون للعقد أطفال. في حالة عدم وجود أطفال ، يطلق عليه اسم ورقة.
هناك قاعدتان يجب اتباعهما:
- يجب أن تكون قيمة كل عقدة أقل أو مساوية لجميع القيم المخزنة في توابعها.
- لديها أقل ارتفاع ممكن.
الأكوام فعالة للغاية في استخراجأصغر أو أكبر عنصر.
دعنا ننتقل إلى كومة دقيقة الآن!
كومة دقيقة
Min heap هو شجرة ثنائية كاملة تكون فيها قيمة العنصر الجذر أقل من أو تساوي أيًا من العنصر الفرعي.
تمثيل دقيقة الكومة
الوصول [(i-1) / 2]: سيؤدي هذا إلى إرجاع العقدة الأصلية.
__init__ في بيثون
الوصول [(2 * i) + 1]: هذا سيعيد العقدة الفرعية اليسرى.
الوصول [(2 * i) + 2]: هذا سيعيد العقدة الفرعية الصحيحة.
هناك طرق معينة لاستخدام Min Heap:
- إدراج(): يضاف مفتاح جديد في نهاية الشجرة. في حال كان المفتاح الجديد أكبر من الأصل ، فلا داعي للقيام بأي شيء ، وإلا علينا الانتقال إلى أعلى لإعداد خاصية الكومة.
- getMin (): تساعد هذه الطرق في إرجاع عنصر الجذر.
- استخراج دقيقة (): هذه الطريقة ترجع الحد الأدنىجزء.
الانتقال إلى ماكس كومة الآن.
ماكس كومة
الحد الأقصى لكومة الذاكرة المؤقتة هو شجرة ثنائية كاملة تكون فيها قيمة العنصر الجذر أكبر من أو تساوي أيًا من العنصر الفرعي.
يتكون Max heap من عدة طرق أيضًا!
- إدراج (): سيتم إدراج عنصر في الكومة.
- حذف() : سيتم حذف عنصر من الكومة.
- FindMax (): سيجد أقصى عنصر من الكومة.
- printHeap (): سيتم طباعة محتوى الكومة
الآن اسمحوا لي أن أريكم تنفيذ الكومة من خلال رسم تخطيطي ولاحقًا Javaالشفرة.
تنفيذ الكومة في Java
رسم بياني:
يوضح الرسم البياني أعلاه الكومة الثنائية في Java. كما تعلمت أن هناك كومة: Min heap و Max heap ، إليك رسم تخطيطي:
كيفية إيقاف برنامج جافا في التعليمات البرمجية
الآن ، بالانتقال إلى الجزء التالي ، سنرى كيفية تنفيذ كومة ثنائية في Java.
الشفرة:
فئة عامة BinaryHeap {private static final int d = 2 int الخاصة [] heap private int heapSize / ** * سيؤدي هذا إلى تهيئة الكومة بالحجم الافتراضي. * / public BinaryHeap (سعة int) {heapSize = 0 heap = new int [السعة + 1] Arrays.fill (heap، -1)} / ** * سيتحقق هذا مما إذا كانت الكومة فارغة أم لا * التعقيد: O ( 1) * / المنطقية العامة isEmpty () {return heapSize == 0} / ** * هذا سوف يتحقق مما إذا كانت الكومة ممتلئة أم لا * التعقيد: O (1) * / public boolean isFull () {return heapSize == heap .length} private int parent (int i) {return (i-1) / d} private int kthChild (int i، int k) {return d * i + k} / ** * سيؤدي هذا إلى إدراج عنصر جديد في الكومة * التعقيد: O (log N) * كأسوأ سيناريو ، نحتاج إلى المرور حتى الجذر * / إدراج الفراغ العام (int x) {if (isFull ()) طرح NoSuchElementException ('Heap ممتلئة ، لا توجد مساحة لإدراجها new element ') heap [heapSize ++] = x heapifyUp (heapSize-1)} / ** * سيؤدي هذا إلى حذف العنصر في الفهرس x * التعقيد: O (log N) * * / public int delete (int x) {if (isEmpty ()) رمي NoSuchElementException الجديد ('الكومة فارغة ، لا يوجد عنصر للحذف') مفتاح int = heap [x] heap [x] = heap [heapSize -1] heapSize-- heapifyDown (x) retu rn key} / ** * تُستخدم هذه الطريقة للحفاظ على خاصية الكومة أثناء إدراج عنصر. * * / heapifyUp (int i) {int temp = heap [i] while (i> 0 && temp> heap [parent (i)]) {heap [i] = heap [parent (i)] i = أحد الوالدين (i)} heap [i] = temp} / ** * تُستخدم هذه الطريقة للحفاظ على خاصية الكومة أثناء حذف عنصر. * * / private void heapifyDown (int i) {int child int temp = heap [i] while (kthChild (i، 1)heap [rightChild]؟ leftChild: rightChild} / ** * هذه الطريقة مستخدمة لطباعة كل عناصر الكومة * * / public void printHeap () {System.out.print ('nHeap =') لـ (int i = 0 iبهذا ، وصلنا إلى نهاية هذه المقالة حول Binary Heap في Java. تفحص ال من Edureka ، وهي شركة تعليمية موثوقة عبر الإنترنت مع شبكة تضم أكثر من 250000 متعلم راضٍ منتشرين في جميع أنحاء العالم. تم تصميم دورة تدريب وشهادة Java J2EE و SOA من Edureka للطلاب والمهنيين الذين يرغبون في أن يصبحوا مطوري Java. تم تصميم الدورة التدريبية لمنحك السبق في برمجة Java وتدريبك على مفاهيم Java الأساسية والمتقدمة جنبًا إلى جنب مع العديد من أطر Java مثل Hibernate & Spring.
لديك سؤال لنا؟ يرجى ذكر ذلك في قسم التعليقات في مدونة 'Java ArrayList' وسنعاود الاتصال بك في أقرب وقت ممكن.