最小堆（Min Heap）是一種特殊的完全二叉樹數據結構，在這種結構中，對于任意節點，其值都小于或等于它的子節點的值。根節點是堆中的最小元素。最小堆常用于實現優先隊列，以及堆排序算法。

在Java中，我們可以使用數組或ArrayList來實現最小堆，因為完全二叉樹的特性允許我們通過簡單的數學運算在數組中找到父節點和子節點的位置。

最小堆的基本操作：

1. 插入元素：將新元素添加到數組的末尾，然后從下至上調整以保持最小堆的性質。
2. 刪除最小元素：移除數組的第一個元素（即堆頂），然后將最后一個元素移到堆頂，再從上至下調整以保持堆的性質。
3. 獲取最小元素：直接訪問數組的第一個元素。

示例代碼：

下面是一個簡單的Java實現最小堆的示例：

import java.util.Arrays;public class MinHeap {private int[] heap;private int size;public MinHeap(int capacity) {heap = new int[capacity];size = 0;}// 插入元素public void insert(int value) {if (size == heap.length) {throw new IllegalStateException("Heap is full");}heap[size] = value;siftUp(size);size++;}// 上浮操作，保持最小堆性質private void siftUp(int index) {while (index > 0) {int parentIndex = (index - 1) / 2;if (heap[parentIndex] > heap[index]) {swap(parentIndex, index);index = parentIndex;} else {break;}}}// 刪除并返回最小元素public int extractMin() {if (size == 0) {throw new IllegalStateException("Heap is empty");}int min = heap[0];heap[0] = heap[size - 1];size--;siftDown(0);return min;}// 下沉操作，保持最小堆性質private void siftDown(int index) {int leftChildIndex = 2 * index + 1;int rightChildIndex = 2 * index + 2;int smallest = index;if (leftChildIndex < size && heap[leftChildIndex] < heap[smallest]) {smallest = leftChildIndex;}if (rightChildIndex < size && heap[rightChildIndex] < heap[smallest]) {smallest = rightChildIndex;}if (smallest != index) {swap(index, smallest);siftDown(smallest);}}// 交換兩個元素private void swap(int i, int j) {int temp = heap[i];heap[i] = heap[j];heap[j] = temp;}// 打印堆的內容public void printHeap() {System.out.println(Arrays.toString(Arrays.copyOf(heap, size)));}
}

使用示例：

public class Main {public static void main(String[] args) {MinHeap heap = new MinHeap(10);heap.insert(10);heap.insert(1);heap.insert(15);heap.insert(5);heap.printHeap(); // 輸出: [1, 5, 10, 15]System.out.println("Extracted min: " + heap.extractMin()); // 輸出: Extracted min: 1heap.printHeap(); // 輸出: [5, 10, 15]}
}

這段代碼創建了一個最小堆，并提供了插入和刪除最小元素的功能。注意，實際應用中可能需要處理堆滿或空的情況，以及可能的異常情況。此外，上述代碼未包含容量自動擴展的邏輯，實際使用時應考慮這一點。

為了使代碼更加健壯和實用，我們可以添加以下功能：

1. 自動擴展堆的容量：當插入元素導致堆溢出時，動態地增加堆的大小。
2. 堆的初始化：提供一個構造函數接受一個數組，可以立即構建一個最小堆。
3. 獲取堆的大小和是否為空的方法。

以下是完善后的代碼：

import java.util.Arrays;public class MinHeap {private int[] heap;private int size;private int capacity;public MinHeap(int capacity) {this.capacity = capacity;heap = new int[capacity];size = 0;}// 構造函數，接收一個數組，構建最小堆public MinHeap(int[] arr) {this(arr.length);for (int value : arr) {insert(value);}}public void insert(int value) {ensureCapacity();heap[size] = value;siftUp(size);size++;}private void ensureCapacity() {if (size == heap.length) {int newCapacity = heap.length * 2;heap = Arrays.copyOf(heap, newCapacity);capacity = newCapacity;}}public int extractMin() {if (size == 0) {throw new IllegalStateException("Heap is empty");}int min = heap[0];heap[0] = heap[size - 1];size--;siftDown(0);return min;}private void siftUp(int index) {while (index > 0) {int parentIndex = (index - 1) / 2;if (heap[parentIndex] > heap[index]) {swap(parentIndex, index);index = parentIndex;} else {break;}}}private void siftDown(int index) {int leftChildIndex = 2 * index + 1;int rightChildIndex = 2 * index + 2;int smallest = index;if (leftChildIndex < size && heap[leftChildIndex] < heap[smallest]) {smallest = leftChildIndex;}if (rightChildIndex < size && heap[rightChildIndex] < heap[smallest]) {smallest = rightChildIndex;}if (smallest != index) {swap(index, smallest);siftDown(smallest);}}private void swap(int i, int j) {int temp = heap[i];heap[i] = heap[j];heap[j] = temp;}public void printHeap() {System.out.println(Arrays.toString(Arrays.copyOf(heap, size)));}public int getSize() {return size;}public boolean isEmpty() {return size == 0;}
}

使用示例：

public class Main {public static void main(String[] args) {int[] arr = {10, 1, 15, 5};MinHeap heap = new MinHeap(arr);System.out.println("Initial heap:");heap.printHeap();System.out.println("\nExtracted min: " + heap.extractMin());System.out.println("Heap after extraction:");heap.printHeap();System.out.println("\nInserting 3:");heap.insert(3);heap.printHeap();System.out.println("\nHeap size: " + heap.getSize());System.out.println("Is heap empty? " + heap.isEmpty());}
}

這個版本的最小堆類現在可以處理動態容量擴展，初始化一個已有元素的堆，以及提供了一些額外的輔助方法。

讓我們通過一個表格逐步演示如何使用上面定義的 MinHeap 類。我們將執行一系列操作，包括插入元素、提取最小元素、檢查堆的狀態等。

初始狀態

Index	Value
0	-
1	-
2	-
3	-
4	-
Size	0

操作 1: 插入元素 10

Index	Value
0	10
1	-
2	-
3	-
4	-
Size	1

操作 2: 插入元素 1

Index	Value
0	1
1	10
2	-
3	-
4	-
Size	2

操作 3: 插入元素 15

Index	Value
0	1
1	10
2	15
3	-
4	-
Size	3

操作 4: 插入元素 5

Index	Value
0	1
1	5
2	10
3	15
4	-
Size	4

操作 5: 提取最小元素

提取后，堆中最小元素（1）被刪除，最后一個元素（15）被移動到堆頂，并進行下沉操作以保持堆的性質。

Index	Value
0	15
1	5
2	10
3	-
4	-
Size	3

進行下沉操作后：

Index	Value
0	5
1	10
2	15
3	-
4	-
Size	3

操作 6: 插入元素 3

Index	Value
0	3
1	5
2	10
3	15
4	-
Size	4

操作 7: 檢查堆的大小和是否為空

• 堆的大小: 4
• 堆是否為空: false

通過這個步驟，我們可以清楚地看到 MinHeap 類是如何管理元素的插入、刪除和維護堆的性質的。