在 Java 中实现最小最大堆

1. Java 中的 Min-Max 堆介绍
2. 在 Java 中使用 PriorityQueue 类和 Collections.reverseOrder() 实现最大堆
3. 在 Java 中使用 PriorityQueue 类实现最小堆

本文将使用 PriorityQueue 类实现一个最大堆和一个最小堆。我们还将演示从堆中插入和删除元素。

Java 中的 Min-Max 堆介绍

堆是一种基于树的数据结构，它形成了一个完整的二叉树。堆被表示为一个数组。有两种类型的堆，它们是最小堆和最大堆。最小堆，也称为最小堆，在其根节点或父节点中具有最小值。类似地，最大堆在根节点或父节点中具有最大值。因此，堆数据结构使得从数组中提取最大和最小元素变得更加容易。我们可以得到 O(1) 中最大和最小的元素。从堆中删除或插入元素的复杂性是 O(log N)。

最小-最大堆是一种包含交替的最小和最大级别的数据结构。根节点包含最小值，其下一层代表最大值。最小值用偶数级别（如 0、2、4）表示。奇数级别（如 1、3、5）表示最大值。

在 Java 中使用 PriorityQueue 类和 Collections.reverseOrder() 实现最大堆

我们可以使用 PriorityQueue 类在 Java 中实现堆。该类默认实现了最小堆，我们可以使用 Collections 中的 reverseOrder() 方法来实现最大堆。我们可以使用 peek() 方法来显示堆中根节点的元素。poll() 方法返回并删除根节点的值。我们可以使用 contains() 方法来检查元素是否存在于堆中。

例如，从 java.util 包中导入所有内容。创建一个类 MaxHeap 并编写 main 方法。然后创建一个 PriorityQueue 类的实例作为 pq。使用泛型类型创建 Integer 实例。在创建对象时在括号中写入 Collections.reverseOrder()。使用 add() 方法将四个整数值相加。使用对象 pq 调用 peek() 方法并打印它。然后，在对象上使用 poll() 方法。接下来，使用值 30 作为参数调用 remove() 方法，然后使用 iterator() 和 hasNext() 方法打印数组中的元素。最后，使用带有参数 20 的 contains() 方法。

在下面的示例中，import java.util.* 将导入我们用来创建最大堆的 PriorityQueue 类。我们将值 1、2、3 和 4 添加到堆中。peek() 方法返回值 4，这是堆中最大的值。然后，poll() 方法删除了最大数字 4。然后，我们使用 remove() 方法删除数字 3，并将剩余的元素打印在堆中。它打印了值 1 和 2，因为我们已经删除了 3 和 4。最后，我们使用 contains() 方法检查堆是否包含数字 2。它返回 true，因为堆中存在该数字。因此，我们使用 PriorityQueue 类和 Collectios.reverseOrder() 实现了最大堆。

示例代码：

import java.util.*;

class MaxHeap {
  public static void main(String args[]) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
    pq.add(1);
    pq.add(3);
    pq.add(2);
    pq.add(4);
    System.out.println("The highest value in the heap:" + pq.peek());
    pq.poll();
    pq.remove(3);
    System.out.println("after removing 3:");
    Iterator<Integer> itr = pq.iterator();
    while (itr3.hasNext()) System.out.println(itr.next());
    boolean b = pq.contains(2);
    System.out.println("Does the heap contains 2 ?" + b);
  }
}

输出：

The highest value in the heap:4
after removing 3:
2
1
Does the heap contains 2 ?true

在 Java 中使用 PriorityQueue 类实现最小堆

PriorityQueue 类默认实现最小堆。我们对最小堆应用与对最大堆相同的实现方法。我们使用与 peek()、remove()、poll() 和 contains() 等相同的方法来执行相同的操作。

在下面的示例中，我们在堆中添加了数字 1、2、3 和 4。peek() 方法返回根节点中的元素，即 1，如输出所示。我们使用 poll() 方法删除根节点元素 1。我们再次使用 remove() 函数从堆中删除了值 3。删除这些值后，我们的堆只包含元素 2 和 4。最后，我们使用 contains() 方法检查堆中的值是否为 3。由于我们已经删除了它，该方法返回一个 false 值。因此，我们使用 PriorityQueue 类实现了一个最小堆。

示例代码：

import java.util.*;

class MinHeap {
  public static void main(String args[]) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    pq.add(1);
    pq.add(3);
    pq.add(2);
    pq.add(4);
    System.out.println("The highest value in the heap:" + pq.peek());
    pq.poll();
    pq.remove(3);
    System.out.println("after removing 3:");
    Iterator<Integer> itr = pq.iterator();
    while (itr.hasNext()) System.out.println(itr.next());
    boolean b = pq.contains(3);
    System.out.println("Does the heap contains 3 ?" + b);
  }
}

输出：

The highest value in the heap:1
after removing 3:
2
4
Does the heap contains 2 ?false