Java 中的最小堆示例

在我們開始之前，假設您了解二叉樹 （在二叉樹中，每個節點存儲一個大於其左子樹中所有鍵且小於其右子樹中所有鍵的鍵）。然而，二叉堆是滿足 最小堆或最大堆排序屬性的完全二叉樹. 如果您不熟悉這些概念，我們建議您先了解這些概念。許多新手程序員可能難以理解堆、最小堆和優先隊列的概念。在這篇文章中，我們將深入探討堆與最小堆的不同之處，以及我們如何使用優先級隊列來實現最小堆。

什麼是最小堆？

最小堆具有以下屬性，即級別“n”的每個節點存儲的值小於或等於級別“n+1”的子節點的值。由於根的值小於或等於其子項，而子項的值又小於或等於其子項，因此根存儲樹中所有值的最小值。

例子

圖 1：一個簡單的最小堆 請注意，在最小堆或最大堆中，節點的值與其兄弟節點的值之間沒有必然關係。例如，根的左子樹中所有節點的值可能都大於右子樹中每個節點的值。 圖 2：左子節點 > 右子節點的最小堆

Java 中最小堆的表示

最常用的表示最小堆的數據結構是一個簡單的數組。作為初學者，您不需要將“數組”與“最小堆”混淆。您可以將其視為最小堆的節點/元素的值存儲在數組中。就像我們在Java中沒有任何數據結構來存儲“樹”而我們為它構建一個“節點”，或者我們使用“地圖”存儲“圖”的方式。 圖 3：圖 2 中堆的數組表示 我們將演示如何使用以下公式簡單地訪問父節點、右子節點或左子節點。

• 令minHeap[]是一個整數數組，其根索引為“ i = 0; ”。
• minHeap[(i - 1) / 2] 返回父節點。
• minHeap[(i * 2) + 2]返回右子節點。
• minHeap[(i * 2) + 1]返回左子節點。

考慮上面給出的圖 #2，根（父節點）= 3，左子節點為 13，右子節點 = 7。

Java中最小堆的實現——使用數組

下面看一下使用數組的Heaps的基本實現，index為當前待添加元素的位置，size為數組的總大小。

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

輸出

優先隊列

優先隊列是一種特殊類型的隊列，其中每個元素都與一個優先級相關聯，並根據其優先級放置。為了更簡單的實現最小堆，我們使用Java提供的PriorityQueue類java.util.PriorityQueue 。如果給定的元素應該按優先級排序/放置，則使用優先級隊列。優先級隊列不同於簡單的隊列，因為標準隊列遵循先進先出（FIFO）算法，但有時需要根據優先級處理隊列的元素，這就是設計優先級隊列的原因。當您將元素添加到優先級隊列時，默認情況下會構建一個最小堆。

常用操作

在我們繼續實施之前，您需要了解java.util.PriorityQueue中的一些常見操作。

• add(int element)將指定的元素插入到優先級隊列中。
• remove(int element)從此隊列中刪除指定元素的單個實例（如果存在）。
• peek()檢索但不刪除此隊列的頭部，或者如果隊列為空則返回 null。
• poll()檢索並移除此隊列的頭部，如果此隊列為空，則返回 null。
• 如果此隊列包含指定元素，則contains()返回“true”。
• size()返回此優先級隊列/最小堆中的元素數。

使用優先級隊列在 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);
	}
}

輸出

結論

最小堆廣泛用於在恆定時間內檢索元素池中的最小元素。這種數據結構還有很多其他應用，但是您可以選擇任何方法來實現它。不用說，您必須耐心練習才能熟練掌握它。因此，讓我們的肌肉活動起來並開始工作吧！