// Path: src/main/java/io/github/marioluan/datastructures/Util.java
// public final class Util {
// 
//     private Util() {
//     }
// 
//     /**
//      * Check whether {@link Comparable a} is lesser than {@link Comparable b}.
//      *
//      * @param a
//      * @param b
//      * @return returns whether a is lesser than b
//      */
//     @SuppressWarnings({ "rawtypes", "unchecked" })
//     public static boolean less(Comparable a, Comparable b) {
//         return a.compareTo(b) < 0;
//     }
// 
//     /**
//      * Check whether {@link a} is lesser than {@link b}.
//      * 
//      * @param <T>
//      * @param a
//      * @param b
//      * @return returns whether a is lesser than b
//      */
//     @SuppressWarnings("unchecked")
//     public static <T> boolean less(T a, T b) {
//         return ((Comparable<T>) a).compareTo(b) < 0;
//     }
// 
//     /**
//      * Check whether {@link Comparable a} is lesser or equal to
//      * {@link Comparable b}.
//      *
//      * @param a
//      * @param b
//      * @return returns whether a is lesser or equal to b
//      */
//     @SuppressWarnings({ "rawtypes", "unchecked" })
//     public static boolean lessOrEqual(Comparable a, Comparable b) {
//         return a.compareTo(b) < 1;
//     }
// 
//     /**
//      * Swap item in position i by item in position j from array {@link a}.
//      *
//      * @param a
//      * @param i
//      * @param j
//      */
//     @SuppressWarnings("rawtypes")
//     public static void swap(Comparable[] a, int i, int j) {
//         Comparable copy = a[i];
//         a[i] = a[j];
//         a[j] = copy;
//     }
// 
//     /**
//      * Swap item in position i by item in position j from array {@link a}.
//      * 
//      * @param <T>
//      * @param a
//      * @param i
//      * @param j
//      */
//     public static <T> void swap(T[] a, int i, int j) {
//         T copy = a[i];
//         a[i] = a[j];
//         a[j] = copy;
//     }
// 
//     /**
//      * Find and return the index from the minimum item from array a within
//      * lowerBound and upperBound.
//      * 
//      * @param a
//      * @param lowerBound
//      * @param upperBound
//      * @return returns the index from the element with the minimum value
//      */
//     @SuppressWarnings("rawtypes")
//     public static int findMin(Comparable[] a, int lowerBound, int upperBound) {
//         int min = lowerBound;
//         for (int i = lowerBound + 1; i < upperBound; i++)
//             if (less(a[i], a[min]))
//                 min = i;
// 
//         return min;
//     }
// 
//     /**
//      * Make a copy of items from array a within lo and hi bounds into array aux.
//      *
//      * @param a
//      * @param aux
//      * @param lo
//      * @param hi
//      */
//     @SuppressWarnings("rawtypes")
//     public static void copy(Comparable[] a, Comparable[] aux, int lo, int hi) {
//         for (int i = lo; i <= hi; i++)
//             aux[i] = a[i];
//     }
// 
//     /**
//      * Make a copy of items from array a within lo and hi bounds into array aux.
//      * 
//      * @param <T>
//      * @param a
//      * @param aux
//      * @param lo
//      * @param hi
//      */
//     public static <T> void copy(T[] a, T[] aux, int lo, int hi) {
//         for (int i = lo; i <= hi; i++)
//             aux[i] = a[i];
//     }
// }


import java.util.Iterator;
import java.util.NoSuchElementException;
import io.github.marioluan.datastructures.Util;
package io.github.marioluan.datastructures.priority.queue;



/**
 * Complete binary tree implementation using a max-heap data structure.<br>
 * TODO: implement resizable functionality.
 * 
 * @author marioluan
 * @param <Key>
 *            the class type of the key being handled
 */
public class MaxBinaryHeap<Key> implements Iterable<Key> {

    private static final int LARGEST_KEY_INDEX = 1;
    private int              n;
    private Key[]            keys;

    /**
     * Construct an empty priority queue.
     * 
     * @param capacity
     */
    @SuppressWarnings("unchecked")
    public MaxBinaryHeap(int capacity) {
        this.keys = (Key[]) new Object[capacity + 1];
        this.n = 0;
    }

    /**
     * Is the heap empty?
     * 
     * @return returns whether it is empty or not
     */
    public boolean isEmpty() {
        return this.n == 0;
    }

    /**
     * Returns the size of the heap.
     * 
     * @return the size
     */
    public int size() {
        return this.n;
    }

    /**
     * Returns (but does not remove) the largest key from the heap.
     * 
     * @return the largest key
     */
    public Key max() {
        return this.keys[LARGEST_KEY_INDEX];
    }

    /**
     * Add the key to the heap by performing an up-heap operation.<br>
     * <strong>Time complexity:</strong> O(log n)
     * 
     * @param key
     */
    public void insert(Key key) {
        if (key == null)
            throw new NullPointerException();

        this.keys[++this.n] = key;
        this.swim(this.n);
    }

    /**
     * Remove and return the max key from the heap by performing a down-heap
     * operation.<br>
     * <strong>Time complexity:</strong> O(log n)
     * 
     * @return the largest key
     */
    public Key delMax() {
        if (this.isEmpty())
            throw new NoSuchElementException();

        Key max = this.keys[LARGEST_KEY_INDEX];
// Path: src/main/java/io/github/marioluan/datastructures/Util.java
// public final class Util {
// 
//     private Util() {
//     }
// 
//     /**
//      * Check whether {@link Comparable a} is lesser than {@link Comparable b}.
//      *
//      * @param a
//      * @param b
//      * @return returns whether a is lesser than b
//      */
//     @SuppressWarnings({ "rawtypes", "unchecked" })
//     public static boolean less(Comparable a, Comparable b) {
//         return a.compareTo(b) < 0;
//     }
// 
//     /**
//      * Check whether {@link a} is lesser than {@link b}.
//      * 
//      * @param <T>
//      * @param a
//      * @param b
//      * @return returns whether a is lesser than b
//      */
//     @SuppressWarnings("unchecked")
//     public static <T> boolean less(T a, T b) {
//         return ((Comparable<T>) a).compareTo(b) < 0;
//     }
// 
//     /**
//      * Check whether {@link Comparable a} is lesser or equal to
//      * {@link Comparable b}.
//      *
//      * @param a
//      * @param b
//      * @return returns whether a is lesser or equal to b
//      */
//     @SuppressWarnings({ "rawtypes", "unchecked" })
//     public static boolean lessOrEqual(Comparable a, Comparable b) {
//         return a.compareTo(b) < 1;
//     }
// 
//     /**
//      * Swap item in position i by item in position j from array {@link a}.
//      *
//      * @param a
//      * @param i
//      * @param j
//      */
//     @SuppressWarnings("rawtypes")
//     public static void swap(Comparable[] a, int i, int j) {
//         Comparable copy = a[i];
//         a[i] = a[j];
//         a[j] = copy;
//     }
// 
//     /**
//      * Swap item in position i by item in position j from array {@link a}.
//      * 
//      * @param <T>
//      * @param a
//      * @param i
//      * @param j
//      */
//     public static <T> void swap(T[] a, int i, int j) {
//         T copy = a[i];
//         a[i] = a[j];
//         a[j] = copy;
//     }
// 
//     /**
//      * Find and return the index from the minimum item from array a within
//      * lowerBound and upperBound.
//      * 
//      * @param a
//      * @param lowerBound
//      * @param upperBound
//      * @return returns the index from the element with the minimum value
//      */
//     @SuppressWarnings("rawtypes")
//     public static int findMin(Comparable[] a, int lowerBound, int upperBound) {
//         int min = lowerBound;
//         for (int i = lowerBound + 1; i < upperBound; i++)
//             if (less(a[i], a[min]))
//                 min = i;
// 
//         return min;
//     }
// 
//     /**
//      * Make a copy of items from array a within lo and hi bounds into array aux.
//      *
//      * @param a
//      * @param aux
//      * @param lo
//      * @param hi
//      */
//     @SuppressWarnings("rawtypes")
//     public static void copy(Comparable[] a, Comparable[] aux, int lo, int hi) {
//         for (int i = lo; i <= hi; i++)
//             aux[i] = a[i];
//     }
// 
//     /**
//      * Make a copy of items from array a within lo and hi bounds into array aux.
//      * 
//      * @param <T>
//      * @param a
//      * @param aux
//      * @param lo
//      * @param hi
//      */
//     public static <T> void copy(T[] a, T[] aux, int lo, int hi) {
//         for (int i = lo; i <= hi; i++)
//             aux[i] = a[i];
//     }
// }


// Path: src/main/java/io/github/marioluan/datastructures/priority/queue/MaxBinaryHeap.java
import java.util.Iterator;
import java.util.NoSuchElementException;
import io.github.marioluan.datastructures.Util;

package io.github.marioluan.datastructures.priority.queue;



/**
 * Complete binary tree implementation using a max-heap data structure.<br>
 * TODO: implement resizable functionality.
 * 
 * @author marioluan
 * @param <Key>
 *            the class type of the key being handled
 */
public class MaxBinaryHeap<Key> implements Iterable<Key> {

    private static final int LARGEST_KEY_INDEX = 1;
    private int              n;
    private Key[]            keys;

    /**
     * Construct an empty priority queue.
     * 
     * @param capacity
     */
    @SuppressWarnings("unchecked")
    public MaxBinaryHeap(int capacity) {
        this.keys = (Key[]) new Object[capacity + 1];
        this.n = 0;
    }

    /**
     * Is the heap empty?
     * 
     * @return returns whether it is empty or not
     */
    public boolean isEmpty() {
        return this.n == 0;
    }

    /**
     * Returns the size of the heap.
     * 
     * @return the size
     */
    public int size() {
        return this.n;
    }

    /**
     * Returns (but does not remove) the largest key from the heap.
     * 
     * @return the largest key
     */
    public Key max() {
        return this.keys[LARGEST_KEY_INDEX];
    }

    /**
     * Add the key to the heap by performing an up-heap operation.<br>
     * <strong>Time complexity:</strong> O(log n)
     * 
     * @param key
     */
    public void insert(Key key) {
        if (key == null)
            throw new NullPointerException();

        this.keys[++this.n] = key;
        this.swim(this.n);
    }

    /**
     * Remove and return the max key from the heap by performing a down-heap
     * operation.<br>
     * <strong>Time complexity:</strong> O(log n)
     * 
     * @return the largest key
     */
    public Key delMax() {
        if (this.isEmpty())
            throw new NoSuchElementException();

        Key max = this.keys[LARGEST_KEY_INDEX];
        Util.swap(this.keys, LARGEST_KEY_INDEX, this.n--);