Min Heap ใน Java พร้อมตัวอย่าง

ก่อนที่เราจะเริ่มต้น สมมติว่าคุณรู้เกี่ยวกับ Binary Tree (ใน Binary Tree แต่ละโหนดเก็บคีย์มากกว่าคีย์ทั้งหมดในทรีย่อยด้านซ้ายและน้อยกว่าคีย์ทั้งหมดในทรีย่อยด้านขวา ) ในขณะที่Binary Heap เป็นไบนารีทรีที่สมบูรณ์ซึ่งเป็นไปตามคุณสมบัติการสั่งซื้อmin-heapหรือmax-heap. หากคุณไม่คุ้นเคยกับแนวคิดเหล่านี้ เราขอแนะนำให้คุณทำความเข้าใจสิ่งเหล่านี้เป็นข้อกำหนดเบื้องต้น โปรแกรมเมอร์มือใหม่หลายคนอาจมีปัญหากับแนวคิดเรื่อง Heaps, Min Heaps และ Priority Queues ในโพสต์นี้ เราจะเจาะลึกเพื่อดูว่าฮีปแตกต่างจาก Min-Heaps อย่างไร และเราจะใช้ Priority Queues เพื่อใช้งาน Min Heaps ได้อย่างไร

Min Heap คืออะไร?

min-heap มีคุณสมบัติที่ทุกโหนดที่ระดับ 'n' เก็บค่าที่น้อยกว่าหรือเท่ากับโหนดย่อยที่ระดับ 'n+1' เนื่องจากรูทมีค่าน้อยกว่าหรือเท่ากับลูกของมัน ซึ่งในทางกลับกันมีค่าน้อยกว่าหรือเท่ากับลูกของมัน รูทจึงเก็บค่าต่ำสุดของค่าทั้งหมดในทรี

ตัวอย่าง

รูปที่ 1: ฮีปขั้นต่ำอย่างง่าย โปรดทราบว่าไม่มีความสัมพันธ์ที่จำเป็นระหว่างค่าของโหนดกับโหนดย่อยในฮีปขั้นต่ำหรือฮีปสูงสุด ตัวอย่างเช่น เป็นไปได้ว่าค่าสำหรับโหนดทั้งหมดในทรีย่อยด้านซ้ายของรูทจะมากกว่าค่าสำหรับทุกโหนดในทรีย่อยด้านขวา รูปที่ 2: ฮีปขั้นต่ำที่มีโหนดลูกด้านซ้าย > โหนดลูกด้านขวา

การเป็นตัวแทนของ Min Heap ใน Java

โครงสร้างข้อมูลที่ใช้บ่อยที่สุดในการแสดง Min Heap คือ Array แบบธรรมดา ในฐานะผู้เริ่มต้น คุณไม่จำเป็นต้องสับสนระหว่าง "อาร์เรย์" กับ "min-heap" คุณสามารถดูได้ว่าค่าของโหนด / องค์ประกอบของ min-heap นั้นถูกเก็บไว้ในอาร์เรย์ เช่นเดียวกับที่เราไม่มีโครงสร้างข้อมูลที่จะจัดเก็บ " ต้นไม้ " ใน Java และเราสร้าง "โหนด" สำหรับมัน หรือวิธีที่เราใช้ "แผนที่" เพื่อจัดเก็บ " กราฟ " รูปที่ 3: การแสดงอาร์เรย์ของ Heap ในรูปที่ 2 เราจะสาธิตวิธีการเข้าถึงโหนดพาเรนต์ โหนดขวาหรือซ้ายโดยใช้สูตรต่อไปนี้

• ให้minHeap[]เป็นอาร์เรย์จำนวนเต็มที่มีรูทที่ดัชนี “ i = 0; ".
• minHeap[(i - 1) / 2] ส่งคืนโหนดหลัก
• minHeap[(i * 2) + 2]ส่งคืนโหนดย่อยที่ถูกต้อง
• minHeap[(i * 2) + 1]ส่งคืนโหนดลูกด้านซ้าย

เมื่อพิจารณาจากรูปที่ # 2 ด้านบน ค่าของรูท (พาเรนต์) = 3 โหนดลูกด้านซ้ายคือ 13 และโหนดลูกด้านขวา = 7

การใช้งาน Min Heap ใน Java - การใช้อาร์เรย์

มาดูการใช้งานพื้นฐานของ 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();
	}
}

เอาต์พุต

คิวลำดับความสำคัญ

Priority Queueคือคิวชนิดพิเศษที่องค์ประกอบแต่ละรายการเชื่อมโยงกับลำดับความสำคัญและวางตามลำดับความสำคัญ เพื่อให้ใช้งาน min heap ได้ง่ายขึ้น เราใช้คลาส PriorityQueue java.util.PriorityQueueที่ Java ให้มา หากองค์ประกอบที่กำหนดควรเรียงลำดับ/จัดลำดับความสำคัญ ระบบจะใช้ Priority Queue Priority Queue แตกต่างจาก Queue แบบธรรมดา เนื่องจากคิวมาตรฐานเป็นไปตามอัลกอริทึม First-In-First-Out ( FIFO ) แต่บางครั้งองค์ประกอบของคิวจำเป็นต้องได้รับการประมวลผลตามลำดับความสำคัญ นั่นคือเหตุผลที่ Priority Queue ได้รับการออกแบบ เมื่อคุณเพิ่มองค์ประกอบในคิวลำดับความสำคัญ ฮีปขั้นต่ำจะถูกสร้างขึ้นตามค่าเริ่มต้น

การดำเนินงานทั่วไป

ก่อนที่เราจะดำเนินการต่อไปนี่คือ การดำเนินการทั่วไปบางอย่างในjava.util.PriorityQueueที่คุณจำเป็นต้องทราบ

• เพิ่ม (องค์ประกอบ int)แทรกองค์ประกอบที่ระบุในคิวลำดับความสำคัญ
• Remove(int element)ลบอินสแตนซ์เดียวขององค์ประกอบที่ระบุออกจากคิวนี้ หากมีอยู่
• peek()เรียก แต่ไม่ได้ลบส่วนหัวของคิวนี้ หรือคืนค่า null หากคิวว่างเปล่า
• การสำรวจความคิดเห็น ()ดึงและลบส่วนหัวของคิวนี้ หรือส่งคืนค่า null หากคิวนี้ว่างเปล่า
• มี ()ส่งคืน "จริง" หากคิวนี้มีองค์ประกอบที่ระบุ
• size()ส่งกลับจำนวนขององค์ประกอบในลำดับความสำคัญคิว/minheap

การใช้งาน Min Heap ใน Java โดยใช้ Priority Queues

นี่คือวิธีที่คุณสามารถใช้ฮีปขั้นต่ำโดยใช้คลาสคิวลำดับความสำคัญโดย 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 heaps ใช้กันอย่างแพร่หลายเพื่อดึงองค์ประกอบที่เล็กที่สุดในพูลขององค์ประกอบในเวลาคงที่ มีแอปพลิเคชันอื่นๆ มากมายสำหรับโครงสร้างข้อมูลนี้ อย่างไรก็ตาม คุณสามารถเลือกวิธีใดก็ได้เพื่อนำไปใช้ จำเป็นต้องพูด คุณต้องฝึกฝนด้วยความอดทนเพื่อให้เก่ง ดังนั้นมาทำให้กล้ามเนื้อของเราได้เคลื่อนไหวและเริ่มทำงานกันเถอะ!