最大堆的建立

最大堆（Max-Heap）是一種二叉堆，其中每個節點的值都不小於其子節點的值。最大堆可以用來維護一個元素序列的近似最大值，因為最大堆的根節點總是序列中的最大元素。

建立最大堆的過程通常稱為「堆化」（heapify），它可以通過以下步驟完成：

1. 初始化堆：如果給定的是一個已經排好序的數組，那麼我們可以將這個數組視為一個最大堆。如果不是，我們需要先對數組進行排序，然後按照最大堆的定義來調整數組。

2. 堆化算法：從最後一個非葉子節點開始，比較該節點與其子節點，如果該節點不是最大值，則交換該節點與其子節點中的最大值，並繼續調整其子節點，直到達到葉節點或堆的定義滿足為止。

以下是建立最大堆的偽代碼：

function heapify(array, n, i)
    largest = i
    left = 2*i + 1
    right = 2*i + 2

    if left < n and array[left] > array[largest]
        largest = left

    if right < n and array[right] > array[largest]
        largest = right

    if largest != i
        swap array[i] with array[largest]
        heapify(array, n, largest)

這個函式會遞歸地從數組的最後一個非葉子節點開始，將數組轉換為最大堆。n是數組的大小，i是當前正在處理的節點的索引。

在Java中，可以使用以下代碼來建立最大堆：

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

    public MaxHeap(int capacity) {
        array = new int[capacity];
        size = 0;
    }

    public void add(int value) {
        if (size == array.length) {
            throw new IllegalStateException("Heap is full");
        }
        array[size] = value;
        int i = size;
        while (i > 0 && array[parent(i)] < array[i]) {
            swap(i, parent(i));
            i = parent(i);
        }
        size++;
    }

    private int parent(int i) {
        return (i - 1) / 2;
    }

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

    public int removeMax() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        int max = array[0];
        array[0] = array[size - 1];
        size--;
        maxHeapify(0);
        return max;
    }

    private void maxHeapify(int i) {
        int largest = i;
        int left = leftChild(i);
        int right = rightChild(i);

        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);
        }
    }

    private int leftChild(int i) {
        return 2 * i + 1;
    }

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

在這個實現中，add方法用於將新元素添加到堆中，並調整堆以確保它保持最大堆的性質。removeMax方法用於移除並返回堆中的最大元素，然後調整堆。maxHeapify方法用於從根節點開始向下調整堆。