مثالوں کے ساتھ جاوا میں کم سے کم ہیپ

اس سے پہلے کہ ہم شروع کریں، یہ فرض کیا جاتا ہے کہ آپ بائنری ٹری کے بارے میں جانتے ہیں (بائنری ٹری میں، ہر نوڈ اپنے بائیں سب ٹری میں موجود تمام کنجیوں سے بڑی اور دائیں ذیلی درخت میں موجود تمام کنجیوں سے کم ایک کلید محفوظ کرتا ہے ) ۔ جبکہ، ایک Binary Heap ایک مکمل بائنری ٹری ہے جو یا تو min-heap یا max-heap آرڈرنگ پراپرٹی کو پورا کرتا ہے ۔ اگر آپ ان تصورات سے واقف نہیں ہیں، تو ہم تجویز کرتے ہیں کہ آپ ان کو بطور شرط سمجھ لیں۔ بہت سے نئے پروگرامرز ہیپس، کم ہیپس اور ترجیحی قطاروں کے تصور کے ساتھ جدوجہد کر سکتے ہیں۔ اس پوسٹ میں ہم یہ دیکھنے کے لیے گہرا غوطہ لگائیں گے کہ ہیپس Min-heaps سے کیسے مختلف ہیں اور ہم Min-Heaps کو لاگو کرنے کے لیے ترجیحی قطاروں کا استعمال کیسے کر سکتے ہیں۔

من ہیپ کیا ہے؟

ایک منٹ ہیپ میں یہ خاصیت ہوتی ہے کہ لیول 'n' پر ہر نوڈ ایک قدر ذخیرہ کرتا ہے جو لیول 'n+1' پر اس کے بچوں سے کم یا اس کے برابر ہے۔ چونکہ جڑ کی قدر اس کے بچوں سے کم یا مساوی ہوتی ہے، جس کے نتیجے میں ان کے بچوں سے کم یا مساوی قدریں ہوتی ہیں، جڑ درخت میں تمام اقدار کی کم از کم ذخیرہ کرتی ہے۔

مثال

شکل 1: ایک سادہ منٹ کا ڈھیر نوٹ کریں کہ نوڈ کی قدر اور اس کے بہن بھائی کے درمیان کم ہیپ یا زیادہ سے زیادہ ہیپ میں کوئی ضروری رشتہ نہیں ہے۔ مثال کے طور پر، یہ ممکن ہے کہ جڑ کے بائیں ذیلی درخت میں تمام نوڈس کی قدریں دائیں ذیلی درخت کے ہر نوڈ کی قدروں سے زیادہ ہوں۔ شکل 2: بائیں چائلڈ نوڈس> رائٹ چائلڈ نوڈس کے ساتھ کم سے کم ہیپ

جاوا میں کم ہیپ کی نمائندگی

کم ہیپ کی نمائندگی کرنے کے لیے سب سے زیادہ استعمال ہونے والا ڈیٹا ڈھانچہ ایک سادہ صف ہے۔ ایک مبتدی کے طور پر آپ کو "سلنی" کو "من ہیپ" کے ساتھ الجھانے کی ضرورت نہیں ہے۔ آپ اسے اس طرح دیکھ سکتے ہیں، ایک min-heap کے نوڈس / عناصر کی قدریں ایک صف میں محفوظ ہیں ۔ بالکل اسی طرح جیسے ہمارے پاس جاوا میں " ٹری " کو ذخیرہ کرنے کے لیے کوئی ڈیٹا ڈھانچہ نہیں ہے اور ہم اس کے لیے "نوڈ" بناتے ہیں، یا جس طرح سے ہم " گراف " کو ذخیرہ کرنے کے لیے "نقشہ" استعمال کرتے ہیں ۔ شکل 3: شکل 2 میں ہیپ کی صف کی نمائندگی ہم یہ دکھانے جا رہے ہیں کہ آپ مندرجہ ذیل فارمولوں کا استعمال کرتے ہوئے والدین، دائیں یا بائیں چائلڈ نوڈس تک کیسے آسانی سے رسائی حاصل کر سکتے ہیں۔

• آئیے minHeap[] انڈیکس میں روٹ کے ساتھ ایک عددی صف ہے “ i = 0; "
• minHeap[(i - 1) / 2] پیرنٹ نوڈ کو لوٹاتا ہے۔
• minHeap[(i * 2) + 2] صحیح چائلڈ نوڈ لوٹاتا ہے۔
• minHeap[(i * 2) + 1] بائیں چائلڈ نوڈ کو لوٹاتا ہے۔

اوپر دی گئی شکل نمبر 2 پر غور کرتے ہوئے، روٹ (والدین) = 3 کی قدر، بائیں چائلڈ نوڈ 13 اور دائیں چائلڈ نوڈ = 7 ہے۔

جاوا میں کم ہیپ کا نفاذ - Arrays کا استعمال

آئیے ارے کا استعمال کرتے ہوئے ہیپس کے بنیادی نفاذ کو دیکھتے ہیں، جس میں شامل کیے جانے والے عنصر کی موجودہ پوزیشن کے طور پر انڈیکس، اور ارے کے کل سائز کے طور پر سائز۔

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 استعمال کرتے ہیں۔ اگر دیے گئے عناصر کو ترجیح میں ترتیب دیا جائے / رکھا جائے تو ترجیحی قطار استعمال کی جاتی ہے۔ ترجیحی قطار ایک سادہ قطار سے مختلف ہوتی ہے کیونکہ معیاری قطاریں فرسٹ-ان-فرسٹ-آؤٹ ( FIFO ) الگورتھم کی پیروی کرتی ہیں، لیکن بعض اوقات قطار کے عناصر کو ترجیح کے مطابق پروسیس کرنے کی ضرورت ہوتی ہے، اسی لیے ترجیحی قطار کو ڈیزائن کیا گیا ہے۔ جب آپ ترجیحی قطار میں عناصر کو شامل کرتے ہیں تو، ایک منٹ ہیپ بطور ڈیفالٹ بنایا جاتا ہے۔

کامن آپریشنز

اس سے پہلے کہ ہم نفاذ کی طرف بڑھیں یہاں java.util.PriorityQueue میں چند عام آپریشنز ہیں جن کے بارے میں آپ کو جاننے کی ضرورت ہے۔

• add(int element) متعین عنصر کو ترجیحی قطار میں داخل کرتا ہے۔
• remove(int element) اس قطار سے مخصوص عنصر کی ایک مثال کو ہٹاتا ہے، اگر یہ موجود ہو۔
• peek() اس قطار کے سر کو بازیافت کرتا ہے، لیکن نہیں ہٹاتا، یا اگر قطار خالی ہے تو null لوٹاتا ہے۔
• poll() اس قطار کے سر کو بازیافت اور ہٹاتا ہے، یا اگر یہ قطار خالی ہے تو null لوٹاتا ہے۔
• contains() "سچ" لوٹاتا ہے اگر اس قطار میں مخصوص عنصر شامل ہو۔
• size() اس ترجیحی قطار/minheap میں عناصر کی تعداد لوٹاتا ہے۔

ترجیحی قطاروں کا استعمال کرتے ہوئے جاوا میں کم ہیپ کا نفاذ

یہاں یہ ہے کہ آپ جاوا کے ذریعہ ترجیحی قطار کی کلاس کا استعمال کرتے ہوئے ایک منٹ ہیپ کو کیسے نافذ کرسکتے ہیں۔

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);
	}
}

آؤٹ پٹ

نتیجہ

کم سے کم ہیپس بڑے پیمانے پر عناصر کے تالاب میں سب سے چھوٹے عنصر کو مستقل وقت میں بازیافت کرنے کے لیے استعمال کیے جاتے ہیں۔ اس ڈیٹا سٹرکچر کی بہت سی دوسری ایپلی کیشنز ہیں، تاہم آپ اسے لاگو کرنے کے لیے کوئی بھی طریقہ منتخب کر سکتے ہیں۔ کہنے کی ضرورت نہیں، آپ کو اس میں اچھا حاصل کرنے کے لیے صبر کے ساتھ مشق کرنا ہوگی۔ تو آئیے اپنے پٹھوں کو حرکت دیں اور کام پر لگیں!