دقيقة كومة في جافا مع أمثلة

قبل أن نبدأ، من المفترض أنك تعرف عن الشجرة الثنائية (في الشجرة الثنائية، تخزن كل عقدة مفتاحًا أكبر من جميع المفاتيح في شجرتها الفرعية اليسرى وأقل من جميع المفاتيح في شجرتها الفرعية اليمنى ) . حيث أن Binary Heap عبارة عن شجرة ثنائية كاملة تلبي إما خاصية طلب الحد الأدنى أو الحد الأقصى للكومة . إذا لم تكن على دراية بهذه المفاهيم، فنوصيك بفهمها كشرط أساسي. يمكن للعديد من المبرمجين المبتدئين أن يواجهوا صعوبة في فهم مفهوم Heaps وMin Heaps وقوائم الانتظار ذات الأولوية. في هذا المنشور، سنتعمق في معرفة مدى اختلاف الكومة الصغيرة عن Min-Heaps وكيف يمكننا استخدام قوائم الانتظار ذات الأولوية لتنفيذ Min-Heaps.

ما هو مين كومة؟

تحتوي الكومة الصغيرة على خاصية مفادها أن كل عقدة في المستوى 'n' تخزن قيمة أقل من أو تساوي قيمة العقد التابعة لها في المستوى 'n+1'. نظرًا لأن الجذر له قيمة أقل من أو تساوي أبنائه، والذين بدورهم لديهم قيم أقل من أو تساوي أبنائهم، يخزن الجذر الحد الأدنى من جميع القيم في الشجرة.

مثال

الشكل 1: كومة دقيقة بسيطة لاحظ أنه لا توجد علاقة ضرورية بين قيمة العقدة وقيمة شقيقتها في الكومة الصغيرة أو الكومة القصوى. على سبيل المثال، من الممكن أن تكون قيم جميع العقد في الشجرة الفرعية اليسرى للجذر أكبر من قيم كل عقدة في الشجرة الفرعية اليمنى. الشكل 2: الحد الأدنى من الكومة مع العقد الفرعية اليسرى > العقد الفرعية اليمنى

تمثيل Min Heap في Java

بنية البيانات الأكثر استخدامًا لتمثيل Min Heap هي مصفوفة بسيطة. كمبتدئ، لا تحتاج إلى الخلط بين "المصفوفة" و"الكومة الصغيرة". يمكنك النظر إلى الأمر على أنه يتم تخزين قيم العقد/عناصر الكومة الصغيرة في مصفوفة . مثلما ليس لدينا أي بنية بيانات لتخزين " شجرة " في Java ونقوم ببناء "عقدة" لها، أو الطريقة التي نستخدم بها "الخريطة" لتخزين "رسم بياني ". الشكل 3: تمثيل صفيف الكومة في الشكل 2 سنوضح كيف يمكنك ببساطة الوصول إلى العقد الرئيسية أو اليمنى أو اليسرى باستخدام الصيغ التالية.

• دع minHeap[] عبارة عن مصفوفة أعداد صحيحة ذات جذر في الفهرس " i = 0; ".
• تقوم minHeap[(i - 1) / 2] بإرجاع العقدة الأصلية.
• تقوم minHeap[(i * 2) + 2] بإرجاع العقدة الفرعية الصحيحة.
• يقوم minHeap[(i * 2) + 1] بإرجاع العقدة الفرعية اليسرى.

بالنظر إلى الشكل رقم 2 الموضح أعلاه، فإن قيمة الجذر (الأصل) = 3، والعقدة الفرعية اليسرى هي 13 والعقدة الفرعية اليمنى = 7.

تنفيذ Min Heap في Java - استخدام المصفوفات

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

import java.util.Arrays;
public class MinHeap
{
	private int[] Heap;
	private int index;
	private int size;

	public MinHeap(int size) {
		this.size = size;
		this.index = 0;
		Heap = new int[size];
	}

	private int parent(int i) {
		return (i - 1) / 2;
	}

	private int leftChild(int i) {
		return (i * 2) + 1;
	}

	private int rightChild(int i) {
		return (i * 2) + 2;
	}

	private boolean isLeaf(int i) {
		if (rightChild(i) >= size || leftChild(i) >= size) {
			return true;
		}
		return false;
	}

	public void insert(int element) {
		if (index >= size) {
			return;
		}
		Heap[index] = element;
		int current = index;

		while (Heap[current] < Heap[parent(current)]) {
			swap(current, parent(current));
			current = parent(current);
		}
		index++;
	}

	// removes and returns the minimum element from the heap
	public int remove() {
     // since its a min heap, so root = minimum
		int popped = Heap[0];
		Heap[0] = Heap[--index];
		minHeapify(0);
		return popped;
	}

	// heapify the node at i
	private void minHeapify(int i) {
	// If the node is a non-leaf node and any of its child is smaller
		if (!isLeaf(i)) {
			if (Heap[i] > Heap[leftChild(i)] ||
                  Heap[i] > Heap[rightChild(i)]) {
				if (Heap[leftChild(i)] < Heap[rightChild(i)]) {
					swap(i, leftChild(i));
					minHeapify(leftChild(i));
				} else {
					swap(i, rightChild(i));
					minHeapify(rightChild(i));
				}
			}
		}
	}

	// builds the min-heap using the minHeapify
	public void minHeap() {
		for (int i = (index - 1 / 2); i >= 1; i--) {
			minHeapify(i);
		}
	}

     // Function to print the contents of the heap
	public void printHeap() {
		for (int i = 0; i < (index / 2); i++) {
			System.out.print("Parent : " + Heap[i]);
			if (leftChild(i) < index)
				System.out.print(" Left : " + Heap[leftChild(i)]);
			if (rightChild(i) < index)
				System.out.print(" Right :" + Heap[rightChild(i)]);
			System.out.println();
		}
	}
	// swaps two nodes of the heap
	private void swap(int x, int y) {
		int tmp;
		tmp = Heap[x];
		Heap[x] = Heap[y];
		Heap[y] = tmp;
	}
	public static void main(String[] arg)
      {
	    MinHeap minHeap = new MinHeap(7);
	    minHeap.insert(3);
	    minHeap.insert(13);
	    minHeap.insert(7);
          minHeap.insert(16);
	    minHeap.insert(21);
	    minHeap.insert(12);
	    minHeap.insert(9);
	    minHeap.minHeap();

	   System.out.println("The Min Heap is : " + Arrays.toString(minHeap.Heap);
	   minHeap.printHeap();
	   System.out.println("\nThe Min Value is : " + minHeap.remove());
	   System.out.println("\nThe Min Heap is :"+ Arrays.toString(minHeap.Heap));
	   minHeap.printHeap();
	}
}

انتاج |

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

قائمة انتظار الأولوية هي نوع خاص من قائمة الانتظار يرتبط فيها كل عنصر بأولوية ويتم وضعه وفقًا لأولويته. لتسهيل تنفيذ الحد الأدنى من الكومة، نستخدم فئة PriorityQueue java.util.PriorityQueue التي توفرها Java. إذا كان من المفترض أن يتم فرز/وضع العناصر المحددة في الأولوية، فسيتم استخدام قائمة انتظار الأولوية. تختلف قائمة الانتظار ذات الأولوية عن قائمة الانتظار البسيطة لأن قوائم الانتظار القياسية تتبع خوارزمية First-In-First-Out ( FIFO )، ولكن في بعض الأحيان تحتاج عناصر قائمة الانتظار إلى المعالجة وفقًا للأولوية، ولهذا السبب تم تصميم قائمة انتظار الأولوية. عند إضافة عناصر إلى قائمة انتظار الأولوية، يتم إنشاء كومة صغيرة بشكل افتراضي.

العمليات المشتركة

قبل أن ننتقل إلى التنفيذ، إليك بعض العمليات الشائعة في java.util.PriorityQueue التي تحتاج إلى معرفتها.

• يقوم add(int element) بإدراج العنصر المحدد في قائمة انتظار الأولوية.
• إزالة (عنصر int) يزيل مثيل واحد للعنصر المحدد من قائمة الانتظار هذه، إذا كان موجودا.
• تسترد الدالة peek() رأس قائمة الانتظار هذه، ولكنها لا تزيلها، أو ترجع قيمة فارغة إذا كانت قائمة الانتظار فارغة.
• يقوم Poll() باسترداد وإزالة رأس قائمة الانتظار هذه، أو إرجاع قيمة فارغة إذا كانت قائمة الانتظار هذه فارغة.
• يحتوي على () يُرجع "صحيح" إذا كانت قائمة الانتظار هذه تحتوي على العنصر المحدد.
• يُرجع size() عدد العناصر في قائمة انتظار الأولوية/minheap.

تنفيذ Min Heap في Java باستخدام قوائم الانتظار ذات الأولوية

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

import java.util.*;

class MinHeapPriorityQueue {

	static PriorityQueue minHeap = new PriorityQueue();

	public static void view() {
		for (Integer x : minHeap) {
			System.out.print(x + " ");
		}
		System.out.println();
	}

	public static void main(String args[]) {
		// using "add" operation to insert elements
		minHeap.add(3);
		System.out.print("minHeap.add(3) = ");
		view();
		minHeap.add(13);
		minHeap.add(7);
		minHeap.add(16);
		minHeap.add(21);
		minHeap.add(12);
		minHeap.add(9);

		// printing Min-Heap
		System.out.print("minHeap.view() = ");
		view();

		// using "peek" method to view the head
		System.out.println("minHeap.peek() = " + minHeap.peek());

		// using "poll" method to remove and retrieve the head
		minHeap.poll();
		System.out.print("minHeap.poll() = ");
		view();

		// using "remove" method to remove specified element
		minHeap.remove(7);
		System.out.print("minHeap.remove(7) = ");
		view();

		// Check if an element is present using contains()
		boolean elementFound = minHeap.contains(11);
		System.out.println("minHeap.contains(11) = " + elementFound);
		elementFound = minHeap.contains(16);
		System.out.println("minHeap.contains(16) = " + elementFound);
	}
}

انتاج |

خاتمة

تُستخدم أكوام Min على نطاق واسع لاسترداد أصغر عنصر في مجموعة من العناصر في وقت ثابت. هناك الكثير من التطبيقات الأخرى لبنية البيانات هذه، ولكن يمكنك اختيار أي طريقة لتنفيذ ذلك. وغني عن القول أنه عليك أن تتدرب بصبر حتى تتقن ذلك. لذلك دعونا نحرك عضلاتنا ونبدأ العمل!