public class MaxHeap<T extends Comparable<T>> {
    private T[] heap; // 堆元素?cái)?shù)組
    private int size; // 堆元素?cái)?shù)量

    @SuppressWarnings("unchecked")
    public MaxHeap(int capacity) {
        heap = (T[]) new Comparable[capacity + 1]; // 數(shù)組下標(biāo)從1開(kāi)始
        size = 0;
    }

    public void insert(T value) {
        if (size == heap.length - 1) {
            resize();
        }

        heap[++size] = value; // 新元素插入到數(shù)組最后
        swim(size); // 上濾操作
    }

    public T deleteMax() {
        if (size == 0) {
            throw new NoSuchElementException();
        }

        T max = heap[1]; // 堆頂元素
        heap[1] = heap[size--]; // 將數(shù)組最后一個(gè)元素替換到堆頂
        sink(1); // 下濾操作
        heap[size + 1] = null; // 釋放舊的堆頂元素

        return max;
    }

    public T getMax() {
        if (size == 0) {
            throw new NoSuchElementException();
        }

        return heap[1];
    }

    public void heapSort(T[] arr) {
        heapify(arr); // 初始化堆
        for (int i = size; i > 0; i--) {
            arr[i - 1] = deleteMax(); // 依次取出堆頂元素
        }
    }

    private void swim(int k) {
        while (k > 1 && heap[k].compareTo(heap[k / 2]) > 0) { // 父節(jié)點(diǎn)小于當(dāng)前節(jié)點(diǎn)，上濾
            swap(k, k / 2);
            k /= 2; // 移動(dòng)到父節(jié)點(diǎn)
        }
    }

    private void sink(int k) {
        while (2 * k <= size) { // 如果有左孩子
            int j = 2 * k;
            if (j < size && heap[j].compareTo(heap[j + 1]) < 0) { // 選擇左右孩子中較大的那個(gè)
                j++;
            }

            if (heap[k].compareTo(heap[j]) >= 0) { // 如果父節(jié)點(diǎn)不小于孩子節(jié)點(diǎn)，下濾結(jié)束
                break;
            }

            swap(k, j); // 父節(jié)點(diǎn)和子節(jié)點(diǎn)交換
            k = j; // 移動(dòng)到子節(jié)點(diǎn)
        }
    }

    private void heapify(T[] arr) {
        heap = (T[]) new Comparable[arr.length + 1];
        size = arr.length;

        System.arraycopy(arr, 0, heap, 1, arr.length); // 復(fù)制數(shù)組元素到堆中

        for (int i = size / 2; i >= 1; i--) { // 倒序下濾，從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始
            sink(i); // 下濾操作
        }
    }

    private void resize() {
        int newSize = heap.length * 2;
        heap = Arrays.copyOf(heap, newSize);
    }

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

MaxHeap<Integer> maxHeap = new MaxHeap<>(10);
maxHeap.insert(3);
maxHeap.insert(1);
maxHeap.insert(4);
maxHeap.insert(1);
maxHeap.insert(5);
System.out.println(maxHeap.deleteMax()); // 輸出：5
System.out.println(maxHeap.getMax()); // 輸出：4

Integer[] arr = {3, 1, 4, 1, 5};
maxHeap.heapSort(arr);
System.out.println(Arrays.toString(arr)); // 輸出：[1, 1, 3, 4, 5]