在 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