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使用array的基本实现，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);
	}
}

输出

结论

最小堆广泛用于在恒定时间内检索元素池中的最小元素。这种数据结构还有很多其他应用，但是您可以选择任何方法来实现它。不用说，您必须耐心练习才能熟练掌握它。因此，让我们的肌肉活动起来并开始工作吧！