எடுத்துக்காட்டுகளுடன் ஜாவாவில் Min Heap

நாங்கள் தொடங்குவதற்கு முன், பைனரி மரத்தைப் பற்றி உங்களுக்குத் தெரியும் என்று கருதப்படுகிறது (ஒரு பைனரி மரத்தில், ஒவ்வொரு முனையும் அதன் இடது சப்ட்ரீயில் உள்ள அனைத்து விசைகளையும் விட பெரிய மற்றும் அதன் வலது சப்ட்ரீயில் உள்ள அனைத்து விசைகளை விட குறைவாகவும் ஒரு விசையை சேமிக்கிறது ) . அதேசமயம் , பைனரி ஹீப் என்பது ஒரு முழுமையான பைனரி மரமாகும்.. இந்தக் கருத்துகளை நீங்கள் அறிந்திருக்கவில்லை என்றால், இதை ஒரு முன்நிபந்தனையாகப் புரிந்து கொள்ளுமாறு பரிந்துரைக்கிறோம். பல புதிய புரோகிராமர்கள் ஹீப்ஸ், மைன் ஹீப்ஸ் மற்றும் முன்னுரிமை வரிசைகளின் கருத்துடன் போராடலாம். இந்த இடுகையில், குவியல்கள் Min-Heaps இலிருந்து எவ்வாறு வேறுபடுகின்றன மற்றும் Min Heaps ஐச் செயல்படுத்த முன்னுரிமை வரிசைகளை எவ்வாறு பயன்படுத்தலாம் என்பதைப் பார்க்க ஆழமாக மூழ்குவோம்.

Min Heap என்றால் என்ன?

ஒரு min-heap ஆனது 'n' மட்டத்தில் உள்ள ஒவ்வொரு முனையும் அதன் குழந்தைகளின் மதிப்பை விட குறைவாகவோ அல்லது சமமாகவோ இருக்கும் மதிப்பை 'n+1' இல் சேமிக்கிறது. ரூட் அதன் குழந்தைகளை விட குறைவான அல்லது சமமான மதிப்பைக் கொண்டிருப்பதால், அது அவர்களின் குழந்தைகளை விட குறைவான அல்லது சமமான மதிப்புகளைக் கொண்டிருப்பதால், வேர் மரத்தில் உள்ள அனைத்து மதிப்புகளின் குறைந்தபட்ச மதிப்பையும் சேமிக்கிறது.

உதாரணமாக

படம் 1: ஒரு எளிய நிமிடக் குவியல் ஒரு கணுவின் மதிப்புக்கும் அதன் உடன்பிறந்தவரின் மதிப்புக்கும் மினி-ஹீப் அல்லது மேக்ஸ்-ஹீப் ஆகியவற்றில் அவசியமான தொடர்பு இல்லை என்பதை நினைவில் கொள்ளவும். எடுத்துக்காட்டாக, ரூட்டின் இடது சப்ட்ரீயில் உள்ள அனைத்து முனைகளுக்கான மதிப்புகள் வலது சப்ட்ரீயின் ஒவ்வொரு முனையின் மதிப்புகளை விட அதிகமாக இருக்கும். படம் 2: இடது சைல்டு நோட்கள் > வலது சைல்டு நோட்களுடன் கூடிய சிறிய குவியல்

ஜாவாவில் Min Heap இன் பிரதிநிதித்துவம்

Min Heap ஐப் பிரதிநிதித்துவப்படுத்த பொதுவாகப் பயன்படுத்தப்படும் தரவு அமைப்பு ஒரு எளிய வரிசை ஆகும். ஒரு தொடக்கக்காரராக நீங்கள் ஒரு "வரிசையை" ஒரு "min-heap" உடன் குழப்ப வேண்டியதில்லை. ஒரு நிமிடக் குவியலின் முனைகள் / உறுப்புகளின் மதிப்புகள் ஒரு வரிசையில் சேமிக்கப்படும் என நீங்கள் பார்க்கலாம் . ஜாவாவில் ஒரு “ ட்ரீ ” யை சேமிப்பதற்கு எங்களிடம் எந்த தரவு அமைப்பும் இல்லை , மேலும் அதற்கு ஒரு “நோட்” அல்லது “ வரைபடத்தை ” சேமிக்க “வரைபடத்தை ” பயன்படுத்தும் விதத்தை உருவாக்குகிறோம். படம் 3: படம் 2 இல் குவியலின் வரிசை பிரதிநிதித்துவம் பின்வரும் சூத்திரங்களைப் பயன்படுத்தி பெற்றோர், வலது அல்லது இடது குழந்தை முனைகளை நீங்கள் எவ்வாறு அணுகலாம் என்பதை நாங்கள் நிரூபிக்கப் போகிறோம்.

• Let minHeap[] என்பது " i = 0 குறியீட்டில் ரூட் கொண்ட ஒரு முழு எண் வரிசை ; ”.
• minHeap[(i - 1) / 2] பெற்றோர் முனையை வழங்குகிறது.
• minHeap[(i * 2) + 2] சரியான சைல்டு நோடை வழங்குகிறது.
• minHeap[(i * 2) + 1] இடது குழந்தை முனையை வழங்குகிறது.

மேலே கொடுக்கப்பட்டுள்ள படம் # 2 ஐக் கருத்தில் கொண்டு, ரூட் (பெற்றோர்) = 3 இன் மதிப்பு, இடது குழந்தை முனை 13 மற்றும் வலது குழந்தை முனை = 7.

ஜாவாவில் Min Heap ஐ செயல்படுத்துதல் - வரிசைகளைப் பயன்படுத்துதல்

வரிசையைப் பயன்படுத்தி Heaps இன் அடிப்படைச் செயலாக்கத்தைப் பார்ப்போம், இதில் சேர்க்கப்பட வேண்டிய உறுப்பின் தற்போதைய நிலை மற்றும் அளவை வரிசையின் மொத்த அளவாகக் கொண்டு.

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

வெளியீடு

முன்னுரிமை வரிசைகள்

முன்னுரிமை வரிசை என்பது ஒரு சிறப்பு வகை வரிசையாகும், இதில் ஒவ்வொரு உறுப்பும் முன்னுரிமையுடன் தொடர்புடையது மற்றும் அதன் முன்னுரிமையின்படி வைக்கப்படுகிறது. min heap ஐ எளிதாக செயல்படுத்த, Java வழங்கும் PriorityQueue வகுப்பை java.util.PriorityQueue ஐப் பயன்படுத்துகிறோம். கொடுக்கப்பட்ட கூறுகள் வரிசைப்படுத்தப்பட வேண்டும்/ முன்னுரிமையில் வைக்கப்பட வேண்டும் என்றால், முன்னுரிமை வரிசை பயன்படுத்தப்படும். முன்னுரிமை வரிசை எளிய வரிசையில் இருந்து வேறுபட்டது, ஏனெனில் நிலையான வரிசைகள் ஃபர்ஸ்ட்-இன்-ஃபர்ஸ்ட்-அவுட் ( FIFO ) வழிமுறையைப் பின்பற்றுகின்றன, ஆனால் சில சமயங்களில் வரிசையின் கூறுகள் முன்னுரிமையின்படி செயலாக்கப்பட வேண்டும், அதனால்தான் முன்னுரிமை வரிசை வடிவமைக்கப்பட்டுள்ளது. முன்னுரிமை வரிசையில் உறுப்புகளைச் சேர்க்கும்போது, ​​ஒரு நிமிடக் குவியல் இயல்பாகவே கட்டமைக்கப்படும்.

பொதுவான செயல்பாடுகள்

செயல்படுத்துவதற்கு முன், நீங்கள் தெரிந்து கொள்ள வேண்டிய java.util.PriorityQueue இல் உள்ள சில பொதுவான செயல்பாடுகள் இங்கே உள்ளன.

• add(int உறுப்பு) குறிப்பிட்ட உறுப்பை முன்னுரிமை வரிசையில் செருகும்.
• நீக்கி(int உறுப்பு) குறிப்பிட்ட உறுப்பின் ஒற்றை நிகழ்வை இந்த வரிசையில் இருந்து நீக்குகிறது.
• peek() இந்த வரிசையின் தலையை மீட்டெடுக்கிறது, ஆனால் அகற்றாது, அல்லது வரிசை காலியாக இருந்தால் பூஜ்யமாக வழங்கும்.
• கருத்துக் கணிப்பு () இந்த வரிசையின் தலையை மீட்டெடுத்து அகற்றும் அல்லது இந்த வரிசை காலியாக இருந்தால் பூஜ்யமாக வழங்கும்.
• இந்த வரிசையில் குறிப்பிடப்பட்ட உறுப்பு இருந்தால், contains() "true" என்பதை வழங்குகிறது.
• அளவு() இந்த முன்னுரிமை வரிசை/மின்ஹீப்பில் உள்ள உறுப்புகளின் எண்ணிக்கையை வழங்குகிறது.

முன்னுரிமை வரிசைகளைப் பயன்படுத்தி Java இல் Min Heap ஐ செயல்படுத்துதல்

ஜாவா மூலம் முன்னுரிமை வரிசை வகுப்பைப் பயன்படுத்தி நிமிடக் குவியலை எவ்வாறு செயல்படுத்தலாம் என்பது இங்கே.

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

வெளியீடு

முடிவுரை

நிலையான நேரத்தில் தனிமங்களின் தொகுப்பில் உள்ள மிகச்சிறிய தனிமத்தை மீட்டெடுக்க மின் குவியல்கள் பரவலாகப் பயன்படுத்தப்படுகின்றன. இந்த தரவு கட்டமைப்பின் பிற பயன்பாடுகள் ஏராளமாக உள்ளன, இருப்பினும் இதை செயல்படுத்த எந்த முறையையும் நீங்கள் தேர்வு செய்யலாம். அதில் தேர்ச்சி பெற பொறுமையுடன் பயிற்சி செய்ய வேண்டும் என்று சொல்ல தேவையில்லை. எனவே நம் தசைகளை நகர்த்தி வேலை செய்யட்டும்!