// Week 15 – Max-heap in an array (indexed from 1), as a priority queue
// Run: java MaxHeap.java
import java.util.Arrays;

public class MaxHeap {
    private int[] a = new int[16]; // a[0] is not used
    private int n = 0;

    // Insertion: put it at the end, then "sift it up" – 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]) {   // while the parent is smaller: swap
            swap(i, i / 2);
            i = i / 2;
        }
    }

    // Removing the maximum: the last element goes into the root, then we "sift it down" – 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;                                // left child
            if (c + 1 <= n && a[c + 1] > a[c]) c++;       // the larger child
            if (a[i] >= a[c]) break;                      // the heap property holds
            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();

        // The built-in priority queue (min-heap); reversed comparison for maximum
        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());
    }
}