مثالن سان جاوا ۾ منٽ هيپ

ان کان اڳ جو اسان شروع ڪريون، اهو فرض ڪيو وڃي ٿو ته توهان بائنري وڻ جي باري ۾ ڄاڻو ٿا (هڪ بائنري وڻ ۾، هر نوڊ پنهنجي کاٻي سب ٽري ۾ سڀني ڪنجين کان وڏي ۽ ان جي ساڄي سب ٽري ۾ سڀني ڪنجين کان گهٽ هڪ ڪنجي محفوظ ڪندو آهي ) . جڏهن ته، هڪ بائنري هيپ هڪ مڪمل بائنري وڻ آهي جيڪو مطمئن ڪري ٿو يا ته منٽ-هيپ يا وڌ-هيپ ترتيب ڏيڻ واري ملڪيت . جيڪڏهن توهان انهن تصورن کان واقف نه آهيو، اسان توهان کي سفارش ڪريون ٿا ته انهن کي لازمي طور تي سمجھو. ڪيترائي نوان پروگرامر هيپس، من هيپس ۽ ترجيحي قطار جي تصور سان جدوجهد ڪري سگهن ٿا. هن پوسٽ ۾ اسان اهو ڏسڻ لاءِ هڪ گہرا غوطه وٺنداسين ته هيپس من-هيپس کان ڪيئن مختلف آهن ۽ اسان ڪيئن استعمال ڪري سگهون ٿا ترجيحي قطارن کي منٽ هيپس کي لاڳو ڪرڻ لاءِ.

منٽ هيپ ڇا آهي؟

هڪ منٽ-هيپ ۾ اها ملڪيت آهي ته هر نوڊ سطح '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 آهي.

جاوا ۾ Min Heap جو نفاذ - 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 class java.util.PriorityQueue جاوا پاران مهيا ڪيل. جيڪڏهن ڏنل عنصرن کي ترجيح ۾ ترتيب/ رکيل هجي ته پوءِ ترجيحي قطار استعمال ڪئي ويندي آهي. هڪ ترجيحي قطار هڪ سادي قطار کان مختلف آهي ڇاڪاڻ ته معياري قطار فرسٽ-ان-فرسٽ-آئوٽ ( FIFO ) الگورتھم جي پيروي ڪندا آهن، پر ڪڏهن ڪڏهن قطار جي عناصر کي ترجيح جي مطابق عمل ڪرڻ جي ضرورت آهي، اهو ئي سبب آهي ته ترجيحي قطار ٺهيل آهي. جڏهن توهان عنصرن کي ترجيحي قطار ۾ شامل ڪيو ٿا، هڪ منٽ هيپ ڊفالٽ طرفان ٺهيل آهي.

عام آپريشن

ان کان اڳ جو اسان عمل ۾ وڃون هتي java.util.PriorityQueue ۾ ڪجھ عام عمل آھن جيڪي توھان کي ڄاڻڻ جي ضرورت آھي.

• add(int element) مخصوص عنصر کي ترجيحي قطار ۾ داخل ڪري ٿو.
• هٽايو (int عنصر) هن قطار مان مخصوص عنصر جي هڪ واحد مثال کي هٽائي ٿو، جيڪڏهن اهو موجود آهي.
• 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);
	}
}

پيداوار

نتيجو

منٽ هيپس وڏي پئماني تي استعمال ڪيا ويندا آهن ننڍا عنصر ٻيهر حاصل ڪرڻ لاءِ عناصر جي تلاءَ ۾ مسلسل وقت ۾. هن ڊيٽا جي جوڙجڪ جون ٻيون به ڪافي ايپليڪيشنون آهن، جڏهن ته توهان هن کي لاڳو ڪرڻ لاءِ ڪو به طريقو چونڊي سگهو ٿا. چوڻ جي ضرورت ناهي، توهان کي صبر سان مشق ڪرڻو پوندو ان تي سٺو حاصل ڪرڻ لاء. سو اچو ته اسان جي عضون کي حرڪت ڏيو ۽ ڪم تي وڃو!