الشجرة الثنائية
في جافا، هناك العديد من أنواع مختلفة من هياكل البيانات. تعتمد الكومة على بنية شجرة تسمى الشجرة الثنائية . تتكون الشجرة الثنائية من عقد، يمكن أن تحتوي كل منها على عقدتين فرعيتين كحد أقصى: تتكون الشجرة الثنائية من عقدة أصلية يمكن أن تحتوي على عقدتين من 0 إلى عقدتين. يمكن أن تحتوي على عقدة فرعية يسرى و/أو عقدة فرعية يمينية، أو لا تحتوي على عقد على الإطلاق. في الشجرة الثنائية الكاملة، يتم ملء جميع العقد باستثناء المستوى الأخير الذي يمكن أن يكون ممتلئًا، ولكن لا يلزم أن يكون ممتلئًا. يمكن أن يحتوي المستوى الأخير، المستوى n، من 1 إلى 2n من العقد، حيث يكون الأول عند n = 0 وهو الجذر.ماكس كومة
ماكس كومة (أو maxheap) هي شجرة ثنائية كاملة . الشيء المهم في الأمر هو أن العقدة الأصلية يجب أن يكون لها قيمة أكبر من أو تساوي قيمة العقد الفرعية اليمنى واليسرى. إذا لم يتم الالتزام بذلك، فلن يكون لديك الحد الأقصى للكومة. من ناحية أخرى، فإن الحد الأدنى للكومة هو العكس حيث يكون الجذر هو أصغر قيمة مع زيادة قيمة العقد المتعاقبة؛ كل عقدة فرعية لها قيمة أكبر من أو تساوي العقدة الأم. إنها أيضًا شجرة ثنائية كاملة. مثال على الحد الأقصى للكومة هو: يمكن بناء الحد الأقصى للكومة من مصفوفة. سيتم التفكير في هذه المجموعة من حيث الشجرة. بالنسبة للكومة، إذا تم تخزين الجذر (العقدة الرئيسية العليا للشجرة) في الموضع (الفهرس) n، فسيتم تعريفه للمصفوفة، theArray ، باسم theArray[n] . وبالتالي، فإن العقدتين الفرعيتين اليمنى واليسرى موجودة في Array[2n+1] و TheArray[2n+2] على التوالي. بالنسبة إلى الكومة القصوى، يكون الجذر عند theArray[0] . بالنسبة للمستوى n، الجذر n = 0: theArr[n] هي العقدة الأصلية theArr[(2*n)+1] هي العقدة الفرعية اليسرى theArr[(2*n)+2] هي العقدة الفرعية اليمنىفئة قائمة الانتظار ذات الأولوية
يمكن تنفيذ الأكوام في Java باستخدام فئة PriorityQueue . يتم استخدام PriorityQueues للعثور على العنصر الأكثر أو الأقل أهمية في المجموعة. يمكن العثور على فئة PriorityQueue في java.util.package . يجب أن تتكون قوائم الأولوية من كائنات قابلة للمقارنة بحيث يتم وضعها بترتيب معين في قائمة الانتظار. يمكن أن تحتوي PriorityQueue على مقارنة بحيث يتم إجراء مقارنة بين الكائنات وتشكيل قائمة الانتظار وفقًا لهذه المقارنة. مثال على ذلك هو:import java.util.Comparator;
import java.util.PriorityQueue;
public class Main
{
public static void main(String[] args) {
// Create PriorityQueue with comparator for ascending order of array length
PriorityQueue intQueue = new PriorityQueue((a,b) -> a - b);
Integer [] array1 = {1, 2, 4, 6, 8, 9};
Integer [] array2 = {3, 6, 9};
Integer [] array3 = {2, 4, 8, 16, 32, 64, 128};
Integer [] array4 = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55};
Integer [] array5 = {4};
//Add the array lengths to intQueue
intQueue.add(array1.length);
intQueue.add(array2.length);
intQueue.add(array3.length);
intQueue.add(array4.length);
intQueue.add(array5.length);
//Write out contents of intQueue as stored
while (intQueue.size() != 0) {
System.out.println(intQueue.remove());
}
}
}
إعطاء الإخراج:
1 3 6 7 11
في هذا المثال، الحجم الافتراضي لـ intQueue هو 11، لذلك لم يتم ذكره (عادةً الوسيطة الأولى قبل المقارنة) وتم تقديم المقارنة على النحو التالي:
(أ،ب) -> أ - ب
سيؤدي هذا إلى إجراء مقارنة بين العناصر الموجودة في intQueue وفرزها إلى أطوال مصفوفة بترتيب تصاعدي.
تنفيذ PriorityQueue لإنشاء الحد الأقصى للكومة
يتم تعيين فئة PriorityQueue افتراضيًا على الحد الأدنى من الكومة بدون مقارنة. الحد الأدنى للكومة هو عكس الحد الأقصى للكومة وبالتالي فإن الجذر هو أصغر قيمة والعقد الفرعية المتعاقبة أكبر أو تساوي الجذر والعقد الأصلية اللاحقة. لهذا السبب، بالنسبة إلى الحد الأقصى من الكومة، من الضروري استخدام ReverseOrder() من إطار عمل مجموعات Java كمقارنة. سيضمن هذا حصولنا على الحد الأقصى للكومة وليس الحد الأدنى للكومة. تحتوي هذه الفئة على توابع مفيدة مثل add() و contains() و remove() و poll() و peek() .طريقة | وصف | تعقيد الوقت |
---|---|---|
إضافة (ي) | يضيف العنصر J في نهاية الشجرة | يا (تسجيل الدخول) |
إزالة (ي) | قم بإزالة القيمة J من الشجرة | على) |
تصويت() | يزيل أقصى عنصر من الشجرة | يا (تسجيل الدخول) |
نظرة خاطفة () | إرجاع العنصر الجذر في أعلى الشجرة | يا(1) |
يحتوي على (ي) | يُرجع صحيحًا إذا كان J في قائمة الانتظار، ويُرجع خطأ إذا لم يكن كذلك | على) |
mport java.util.Collections;
import java.util.PriorityQueue;
public class MaxHeap {
public static void writeQueue(PriorityQueue<Integer> priorityQueue)
{
// Write out elements in queue, priorityQueue, and remove them using poll()
while(priorityQueue.size() != 0)
{
System.out.println(priorityQueue.poll());
}
}
public static void writeMaxHeap(PriorityQueue<Integer> priorityQueue)
{
// Write out elements in queue as a max heap - root, left child, right child, etc
for (Integer element : priorityQueue) {
System.out.println(element);
}
}
public static void main(String args[])
{
// Array of numbers to create a max heap array from
int[] theArray = {5, 3, 13, 10, 99, 19, 6, 51, 9};
// theQueue is created
PriorityQueue<Integer> theQueue =
new PriorityQueue<Integer>(Collections.reverseOrder());
// Elements are added to theQueue
for (int i = 0 ; i <theArray.length; ++i)
{
theQueue.add(theArray[i]);
}
// The head or root element (priority element) is printed out
System.out.println("The root value is : " + theQueue.peek());
// Find size of theQueue. Use method size()
Integer s = theQueue.size();
System.out.println("Size of theQueue? " + s);
// All elements of theQueue are printed in terms of parent,
// left child, right child
System.out.println("theQueue written using for loop:");
writeMaxHeap(theQueue);
// Does theQueue contain 10? Use method contains()
boolean b = theQueue.contains(10);
System.out.println("Does theQueue contain 10? " + b);
// Erasing value 10 from array using remove()
theQueue.remove(10);
// All elements of theQueue are printed out and removed.
// Each one is the maximum value left in the queue.
// At the end theQueue will be empty
System.out.println("theQueue written out using poll():");
writeQueue(theQueue);
// Find size of theQueue. Use method size()
s = theQueue.size();
System.out.println("Size of theQueue? " + s);
}
}
انتاج:
القيمة الجذرية هي: 99 حجم قائمة الانتظار؟ 9 قائمة الانتظار مكتوبة باستخدام حلقة 99 51 19 13 10 5 6 3 9 هل تحتوي قائمة الانتظار على 10؟ صحيح أن قائمة الانتظار مكتوبة باستخدام الاستطلاع () 99 51 19 13 9 6 5 3 حجم قائمة الانتظار؟ 0
ماكس هيابيفي
يتم استخدام خوارزمية Max Heapify للتأكد من أن الشجرة الثنائية هي الحد الأقصى للكومة. إذا كنا عند عقدة، n، والعقد التابعة لها، اليسار واليمين، هي أيضًا الحد الأقصى للأكوام بحد ذاتها، فهذا رائع، لدينا الحد الأقصى للكومة. إذا لم يكن هذا هو الحال في جميع أنحاء الشجرة، فلن يكون لدينا الحد الأقصى للكومة. يتم استخدام خوارزمية Max Heapify لفرز الشجرة بحيث تلتزم بمبادئ maxheap. يعمل Max Heapify على عقدة واحدة فقط. إذا كان المتطلب هو أن يكون المصفوفة عبارة عن مصفوفة ذات الحد الأقصى للكومة، فيجب تحويل جميع الأشجار الفرعية إلى الحد الأقصى للكومة قبل الجذر، واحدة تلو الأخرى. يجب استخدام الخوارزمية في كل عقدة. سيتم ذلك على العقد N/2 (ستلتزم الأوراق بالحد الأقصى لمتطلبات الكومة). التعقيد الزمني للكومة هو O(NlogN)، وبالنسبة لعقدة واحدة عند الارتفاع X، يكون التعقيد الزمني هو O(X). يوضح التعليمة البرمجية التالية كيفية تكديس شجرة (مصفوفة) إلى الحد الأقصى.public class MaxHeapify
{
public static Integer[] maxHeapify(Integer[ ] array, Integer i)
{
// Create left-child and right-child for the node in question
Integer leftChild = 2 * i + 1;
Integer rightChild = 2 * i + 2;
// Assign maxVal to parent node, i
Integer maxVal = i;
// Set maxVal to greater of the two: node or left-child
if( leftChild < array.length && array[leftChild] > array[maxVal] )
maxVal = leftChild;
// Set maxVal to greater of the two: maxVal or right-child
if( rightChild < array.length && array[rightChild] > array[maxVal] )
maxVal = rightChild;
// Check if maxVal is not equal to parent node, then set parent node to
// maxVal, swap values and then do a maxheapify on maxVal
// which is now the previous parent node
if( maxVal != i )
{
Integer value = array[i];
array[i] = array[maxVal];
array[maxVal] = value;
array = maxHeapify(array, maxVal);
}
return array;
}
public static Integer[] maxHeapCreate(Integer array[])
{
// Call maxHeapify to arrange array in a max heap
Integer [] theNewArr = array;
for( Integer i = array.length/2; i >= 0; i-- )
theNewArr = maxHeapify(array, i);
return theNewArr;
}
public static void main(String[] args)
{
// Create array to be maxheapified, theArray,
// and array, newArray, to write results into, by calling maxheapCreate
// newArray will now be a maxheap
Integer[] theArray = {5, 3, 13, 10, 99, 19, 6, 51, 9};
Integer[ ] newArray = maxHeapCreate(theArray);
// Print out contents of newArray
System.out.println("newArray:");
for(int i = 0; i < newArray.length; ++i)
{
System.out.println(newArray[i]);
}
// Print out labelled contents of newArray
System.out.println(" root : " + newArray[0]);
for (int i = 0; i <= newArray.length/2 - 1; i++) {
System.out.print(" parent node : " + newArray[i] + " left child : " +
newArray[(2*i)+1] + " right child :" + newArray[(2*i)+2]);
System.out.println();
}
}
}
إعطاء الإخراج:
newArray: 99 51 19 10 3 13 6 5 9 الجذر: 99 العقدة الأصلية: 99 الطفل الأيسر: 51 الطفل الأيمن: 19 العقدة الأصلية: 51 الطفل الأيسر: 10 الطفل الأيمن: 3 العقدة الأصلية: 19 الطفل الأيسر: 13 الطفل الأيمن: 6 العقدة الأصلية: 10 الطفل الأيسر: 5 الطفل الأيمن: 9
في هذا الكود، يتم إنشاء المصفوفة وملؤها بالأرقام. يتم إنشاء مصفوفة ثانية، newArray ، وهذه المرة ستحتوي على نتيجة الطريقة، maxheapCreate ، مصفوفة الكومة القصوى. يتم استدعاء الأسلوب maxHeapCreate من main ، وهنا يتم إنشاء مصفوفة جديدة، theNewArr ، وملؤها بنتائج maxHeapify . يتم ذلك عن طريق تنفيذ حلقات تزيد عن نصف حجم مصفوفة الإدخال. لكل تمريرة من الحلقة، يتم استدعاء الطريقة maxHeapify بدءًا من العنصر الموجود في منتصف المصفوفة وانتهاءً بالعنصر الأول. لكل استدعاء لـ maxHeapify ، يتم العثور على الطفل الأيسر والطفل الأيمن للعقدة الأصلية، i، ويتم إجراء عمليات التحقق للعثور على الأكبر من بين الثلاثة، مع تحديد ذلك على أنه maxVal . إذا كان maxVal لا يساوي العقدة الأصلية، فسيتم إجراء مبادلة بحيث يتم تبديل العقدة الأصلية و maxVal ثم يتم استدعاء maxHeapify مرة أخرى هذه المرة على maxVal ويتم تنفيذ نفس الخطوات كما كان من قبل. في النهاية سيتم إنشاء الحد الأقصى للكومة ولن يكون هناك المزيد من التكرارات لتنفيذها. يتم الآن إرجاع المصفوفة المحدثة، array ، إلى main باسم newArray ثم تتم طباعة كل عنصر متتالي على وحدة التحكم. newArray الآن هو الحد الأقصى للكومة. لاحظ أنه كما في المثال السابق باستخدام PriorityQueue ، يتم كتابة الأرقام: الجذر، الطفل الأيمن للجذر كوالد، الطفل الأيسر للجذر كوالد، الطفل الأيمن للجذر الأول كوالد، الطفل الأيسر للجذر الأول الطفل الأيسر كوالد، والطفل الأيمن للطفل الأيسر الأول كوالد، والطفل الأيسر للطفل الأول الأيمن كوالد، وما إلى ذلك. وهي بترتيب مختلف قليلاً عن تلك عند استخدام PriorityQueue لأن المقارنة تتم بين العناصر المتتالية بينما في مثال maxheapify، تتم مقارنة العقدة بالعنصرين المتتاليين التاليين في المصفوفة ويتم تبديلها للحصول على القيمة الأكبر. باختصار، يتم استخدام خوارزميتين مختلفتين. كلاهما ينشئان الحد الأقصى للكومة.
GO TO FULL VERSION