在 Java 中實現最小堆

Rupam Yadav 2023年10月12日

Java Java Heap

Java 中不使用庫的最小堆實現
Java 中使用 PriorityQueue 實現最小堆

最小堆是其中每個內部節點都小於或等於其子節點值的堆。我們將在以下幾點中看到如何使用和不使用庫來實現最小堆。

Java 中不使用庫的最小堆實現

在這個例子中，我們看到了不使用任何庫的實現。在這裡，我們建立了一個類 JavaMinHeap，我們在其中建立了三個例項變數 HeapArray 是一個 int 型別的陣列，它將保留堆的所有值，size 是堆的大小，maxSize 儲存 HeapArray 的最大大小。我們還建立了一個型別為 int 的 static 變數 FRONT 並將其初始化為 1。

我們在建構函式中獲取 maxSize 作為引數並將其儲存在例項變數 maxSize 中。我們用 0 初始化 size，用 maxSize + 1 大小的 int 陣列初始化 HeapArray。我們將 Integer 的最小值儲存在 HeapArray 的第一個索引處。

現在我們建立方法來在堆上執行操作。parent() 函式將 position 作為引數，並返回節點所傳遞位置的父節點。然後我們建立 leftChild()，它返回作為引數接收到的位置的左孩子。使用 rightChild() 返回 (2 * position) + 1 節點值的右子節點也是如此。

isLeaf() 檢查一個節點是否是葉子節點，這意味著它有任何子節點。swapNodes() 是一種將位置 fpos 的節點值與位置 spos 交換的方法。在方法中，我們建立了一個 temp 變數並初始化它，HeapArray 的 fpos 位置，並將 HeapArray 的 spos 值儲存到 HeapArray[fpos]。現在我們將 temp 值儲存在 HeapArray[spos] 中。

convertToMinHeap() 使用 isLeaf 檢查作為引數接收的位置是否是葉子，如果不是，則檢查 HeapArray 位置的當前值是否大於左孩子或右孩子。然後我們檢查左孩子是否小於右孩子，如果是，我們使用 swapNodes() 來交換節點並在 position 處傳遞 position 和左孩子。我們再次使用 convertToMinHeap() 將接收到的左子節點轉換為最小堆。

我們使用 insert() 將值插入到最小堆中。在 insert() 中，如果陣列達到 maxSize，我們不插入就返回；如果沒有，我們在 ++size 處獲取位置並將接收到的元素插入 HeapArray[++size]。我們把尺寸放到當前。如果當前位置的元素小於其父元素，我們將建立一個迴圈並交換節點。

為了列印最小堆，我們建立 printheap() 並迴圈遍歷 HeapArray，其中父項位於 ith 位置，左子項位於 2 * i 位置，右子項是在 2 * i + 1 位置。在 main() 函式中，我們使用 insert() 在堆中插入元素。

public class JavaMinHeap {
  private final int[] HeapArray;
  private int size;
  private final int maxsize;

  private static final int FRONT = 1;

  public JavaMinHeap(int maxsize) {
    this.maxsize = maxsize;
    this.size = 0;
    HeapArray = new int[this.maxsize + 1];
    HeapArray[0] = Integer.MIN_VALUE;
  }

  private int parent(int position) {
    return position / 2;
  }

  private int leftChild(int position) {
    return (2 * position);
  }

  private int rightChild(int position) {
    return (2 * position) + 1;
  }

  private boolean isLeaf(int position) {
    if (position >= (size / 2) && position <= size) {
      return true;
    }
    return false;
  }

  private void swapNodes(int fpos, int spos) {
    int temp;
    temp = HeapArray[fpos];
    HeapArray[fpos] = HeapArray[spos];
    HeapArray[spos] = temp;
  }

  private void convertToMinHeap(int position) {
    if (!isLeaf(position)) {
      if (HeapArray[position] > HeapArray[leftChild(position)]
          || HeapArray[position] > HeapArray[rightChild(position)]) {
        if (HeapArray[leftChild(position)] < HeapArray[rightChild(position)]) {
          swapNodes(position, leftChild(position));
          convertToMinHeap(leftChild(position));
        } else {
          swapNodes(position, rightChild(position));
          convertToMinHeap(rightChild(position));
        }
      }
    }
  }

  public void insert(int element) {
    if (size >= maxsize) {
      return;
    }
    HeapArray[++size] = element;
    int current = size;

    while (HeapArray[current] < HeapArray[parent(current)]) {
      swapNodes(current, parent(current));
      current = parent(current);
    }
  }

  public void printHeap() {
    for (int i = 1; i <= size / 2; i++) {
      System.out.println("PARENT : " + HeapArray[i]);

      System.out.println("--LEFT CHILD : " + HeapArray[2 * i]);

      System.out.println("--RIGHT CHILD : " + HeapArray[2 * i + 1]);
      System.out.println();
    }
  }

  public static void main(String[] arg) {
    System.out.println("The Min Heap is ");
    JavaMinHeap minHeap = new JavaMinHeap(10);
    minHeap.insert(10);
    minHeap.insert(2);
    minHeap.insert(7);
    minHeap.insert(15);
    minHeap.insert(90);
    minHeap.insert(19);
    minHeap.insert(8);
    minHeap.insert(22);
    minHeap.insert(9);

    minHeap.printHeap();
  }
}

輸出：

The Min Heap is 
PARENT : 2
--LEFT CHILD : 9
--RIGHT CHILD : 7

PARENT : 9
--LEFT CHILD : 10
--RIGHT CHILD : 90

PARENT : 7
--LEFT CHILD : 19
--RIGHT CHILD : 8

PARENT : 10
--LEFT CHILD : 22
--RIGHT CHILD : 15

Java 中使用 `PriorityQueue` 實現最小堆

在這個程式中，我們使用用於建立最大和最小堆的 PriorityQueue。PriorityQueue 提供了多個類似 add() 將元素插入佇列的方法，peek() 獲取佇列的頭部並將其刪除，poll() 也檢索佇列的頭部但不刪除它. contains() 檢查它指定的元素是佇列。remove() 刪除指定的元素。

我們結合 PriorityQueue 的所有功能來建立和執行最小堆操作。首先，我們使用 new PriorityQueue() 建立一個 Integer 型別的空 priorityQueue 物件。然後我們使用 add() 方法新增我們的元素。為了列印和移除佇列頭，我們呼叫列印 10 的 priorityQueue.peek()。然後我們使用增強的 for 列印佇列的所有元素。現在我們呼叫 poll() 列印並刪除 10。然後我們從佇列中刪除一個元素。我們使用返回 boolean 的 contains() 來檢查元素是否在佇列中。最後，為了列印剩餘的值，我們使用 toArray() 將佇列轉換為陣列。

import java.util.*;

public class JavaMinHeap {
  public static void main(String[] args) {
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

    priorityQueue.add(10);
    priorityQueue.add(15);
    priorityQueue.add(25);
    priorityQueue.add(200);

    System.out.println("The head value using peek(): " + priorityQueue.peek());

    System.out.println("The queue elements: ");
    for (Integer integer : priorityQueue) System.out.println(integer);

    priorityQueue.poll();
    System.out.println("After removing the head element using poll(): ");
    for (Integer integer : priorityQueue) System.out.println(integer);

    priorityQueue.remove(25);
    System.out.println("After removing 25 with remove(): ");
    for (Integer integer : priorityQueue) System.out.println(integer);

    boolean b = priorityQueue.contains(15);
    System.out.println("Check if priorityQueue contains 15 using contains():  " + b);

    Object[] arr = priorityQueue.toArray();
    System.out.println("Values in array: ");
    for (Object o : arr) System.out.println("Value: " + o.toString());
  }
}

輸出：

The head value using peek(): 10
The queue elements: 
10
15
25
200
After removing the head element using poll(): 
15
200
25
After removing 25 with remove(): 
15
200
Check if priorityQueue contains 15 using contains():  true
Values in array: 
Value: 15
Value: 200

作者： Rupam Yadav

Rupam Saini is an android developer, who also works sometimes as a web developer., He likes to read books and write about various things.

Java 中不使用庫的最小堆實現

Java 中使用 PriorityQueue 實現最小堆

相關文章 - Java Heap

Java 中使用 `PriorityQueue` 實現最小堆