最大堆數組實現

最大堆（Max-Heap）是一種二叉堆，其中每個父節點的值都不小於其子節點的值。最大堆可以用來實現一個高效的優先佇列，其中隊首元素總是堆中值最大的元素。

在Java中，可以使用一個陣列來實現最大堆。以下是一個簡單的實現：

import java.util.Arrays;

public class MaxHeap {
    private int[] array;
    private int size;

    public MaxHeap(int capacity) {
        this.array = new int[capacity + 1]; // 陣列中額外的一個元素用於存放堆頂
        this.size = 0;
    }

    public void insert(int value) {
        if (size == array.length - 1) {
            throw new IllegalStateException("Heap is full");
        }
        size++;
        array[size] = value;
        int parentIndex = (size - 1) / 2; // 找到父節點的索引
        while (parentIndex >= 0 && array[parentIndex] < array[size]) {
            swap(parentIndex, size);
            parentIndex = (parentIndex - 1) / 2; // 更新父節點的索引
        }
    }

    public int extractMax() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        int max = array[1]; // 堆頂元素
        swap(1, size);
        size--;
        int childIndex = 1; // 找到左子節點的索引
        while (childIndex * 2 <= size) {
            int maxChildIndex = 2 * childIndex; // 找到較大的子節點的索引
            if (maxChildIndex < size && array[maxChildIndex] < array[maxChildIndex + 1]) {
                maxChildIndex++; // 右子節點較大
            }
            if (array[childIndex] <= array[maxChildIndex]) {
                break; // 子節點都不小於父節點，堆結構已保持
            } else {
                swap(childIndex, maxChildIndex);
                childIndex = maxChildIndex;
            }
        }
        return max;
    }

    private void swap(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void buildHeap(int[] values) {
        this.size = values.length;
        System.arraycopy(values, 0, array, 1, size); // 將陣列拷貝到堆中，從索引1開始
        for (int i = size / 2; i >= 1; i--) {
            maxHeapify(i); // 從中間向兩邊遞歸地調整堆結構
        }
    }

    private void maxHeapify(int i) {
        int largest = i;
        int left = 2 * i;
        int right = 2 * i + 1;
        if (left <= size && array[left] > array[largest]) {
            largest = left;
        }
        if (right <= size && array[right] > array[largest]) {
            largest = right;
        }
        if (largest != i) {
            swap(i, largest);
            maxHeapify(largest);
        }
    }

    public void printHeap() {
        System.out.println(Arrays.toString(array));
    }
}

這個類別定義了一個最大堆，可以插入元素、提取最大元素、構建最大堆和列印堆結構。注意，陣列中額外的一個元素用於存放堆頂，所以堆的實際大小是陣列長度減1。

使用這個類別的示例：

MaxHeap maxHeap = new MaxHeap(10);
maxHeap.insert(10);
maxHeap.insert(5);
maxHeap.insert(15);
maxHeap.insert(20);
maxHeap.insert(3);
maxHeap.insert(7);
maxHeap.insert(12);
maxHeap.printHeap(); // 輸出堆結構
System.out.println(maxHeap.extractMax()); // 提取最大元素
maxHeap.printHeap(); // 再次輸出堆結構

輸出：

[3, 5, 7, 10, 12, 15, 20]
20
[3, 5, 7, 10, 12, 15]