// 第 15 周 – 用数组（下标从 1 开始）实现的大顶堆，用作优先队列
// 运行：java MaxHeap.java
import java.util.Arrays;

public class MaxHeap {
    private int[] a = new int[16]; // 不使用 a[0]
    private int n = 0;

    // 插入：放到末尾，然后“上浮” – O(log n)
    void insert(int x) {
        if (n + 1 == a.length) a = Arrays.copyOf(a, 2 * a.length);
        a[++n] = x;
        int i = n;
        while (i > 1 && a[i / 2] < a[i]) {   // 只要父结点更小：交换
            swap(i, i / 2);
            i = i / 2;
        }
    }

    // 取出最大值：把最后一个元素放到根上，然后“下沉” – O(log n)
    int removeMax() {
        if (n == 0) throw new IllegalStateException("empty heap");
        int max = a[1];
        a[1] = a[n--];
        siftDown(1);
        return max;
    }

    private void siftDown(int i) {
        while (2 * i <= n) {
            int c = 2 * i;                                // 左孩子
            if (c + 1 <= n && a[c + 1] > a[c]) c++;       // 较大的孩子
            if (a[i] >= a[c]) break;                      // 满足堆性质
            swap(i, c);
            i = c;
        }
    }

    int max() { return a[1]; }
    boolean isEmpty() { return n == 0; }

    private void swap(int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    String array() { return Arrays.toString(Arrays.copyOfRange(a, 1, n + 1)); }

    public static void main(String[] args) {
        MaxHeap h = new MaxHeap();
        for (int x : new int[] { 40, 70, 20, 90, 50, 80, 60 }) {
            h.insert(x);
            System.out.printf("insert(%d): %s%n", x, h.array());
        }
        h.insert(85);
        System.out.println("insert(85): " + h.array() + "   <- 85 sifted up to position 2");
        System.out.print("removeMax sequence: ");
        while (!h.isEmpty()) System.out.print(h.removeMax() + " ");
        System.out.println();

        // 内置的优先队列（小顶堆）；求最大值时把比较反过来
        java.util.PriorityQueue<Integer> pq = new java.util.PriorityQueue<>(java.util.Comparator.reverseOrder());
        for (int x : new int[] { 40, 70, 20, 90 }) pq.offer(x);
        System.out.println("PriorityQueue (max): poll = " + pq.poll() + ", peek = " + pq.peek());
    }
}