import java.util.AbstractQueue;
import java.util.Iterator;
import java.util.Random;

import java.util.NoSuchElementException;

import static java.lang.Math.max;

class MaxBinaryHeap<T extends Comparable<? super T>>
        extends AbstractQueue<T> {
    private static final int MIN_HEIGHT = 1;

    private T[] data;
    // the number of elements stored in the queue (not including the
    // 0-th null element) and simultaneously the index of the
    // last non-null element in the `data` array
    private int size;
    
    @SuppressWarnings("unchecked")
    public MaxBinaryHeap() {
        data = (T[]) new Comparable<?>[1 << MIN_HEIGHT];
    }
    
    @SuppressWarnings("unchecked")
    private MaxBinaryHeap(T[] data, int size) {
        T[] newData = (T[]) new Comparable<?>[data.length];
        System.arraycopy(data, 0, newData, 0, data.length);
        this.data = newData;
        this.size = size;
    }
    
    @Override
    public boolean offer(T value) {
        grow(1);
        // put the element at the end of the heap
        // and swim it to the proper position
        size++;
        data[size] = value;
        swim(size);
        return true;
    }
    
    @Override
    public T poll() {
        if (size == 0) {
            return null;
        }
        // swap the first and the last elements
        swap(data, 1, size);
        T value = data[size];
        data[size] = null;
        size--;
        // and lower the element that is out of place
        // to the proper position
        if (size > 1) {
            sink(1);
        }

        shrink();
        return value;
    }
    
    @Override
    public T peek() {
        if (size == 0) {
            return null;
        }
        return data[1];
    }
    
    @Override
    public int size() {
        return size;
    }
    
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public Iterator<T> iterator() {
        return new QueueIterator();
    }
    
    /**
     * In case the key of the element at the position `index` is
     * too large this method swims the specified element up to
     * its proper position, simultaniously maintaining the heap
     * ordering.
     */
    private void swim(int index) {
        assert index >= 1 && index <= size;

        while (index > 1 && less(data, index / 2, index)) {
            swap(data, index / 2, index);
            index /= 2;
        }
    }
    
    /**
     * In case the key of the element at the position `index` is too
     * large this method sinks the specified element down to its place.
     */
    private void sink(int index) {
        assert index >= 1 && index <= size;

        while (2 * index <= size) {
            // choose the max child to preserve the heap oredering
            int iMaxChild = 2 * index;
            if (iMaxChild + 1 <= size 
                    && less(data, iMaxChild, iMaxChild + 1)) {
                iMaxChild = iMaxChild + 1;
            }
            // data[index] >= data[iMaxChild]
            if (!less(data, index, iMaxChild)) {
                break;
            }
            swap(data, index, iMaxChild);
            index = iMaxChild;
        }
    }
    
    /**
     * Updates the length of the `data` array, so that it could fit
     * `by` more added elements
     */
    private void grow(int by) {
        if (size + by + 1 > data.length) {
            // the exact size of the array needed to store all elements:
            // size = 2^(floor(lgN) + 1) - 1
            // +1 for the 0-th null element
            int newSize = 1 << log2(size + by) + 1;
            reallocate(max(1 << MIN_HEIGHT, newSize));
        }
    }
    
    /**
     * Shrinks the array in size, so that it would be approximately
     * 50% full.
     */
    private void shrink() {
        int newSize = 1 << log2(size) + 1;
        if (size + 1 <= data.length / 4) {
            reallocate(max(1 << MIN_HEIGHT, newSize));
        }
    }

    /**
     * Copies the meaningful contents of the `data` array into a
     * new array of size `newSize`.
     */
    @SuppressWarnings("unchecked")
    private void reallocate(int newSize) {
        assert newSize >= size;
        
        T[] newData = (T[]) new Comparable<?>[newSize];
        System.arraycopy(data, 0, newData, 0, size + 1);
        data = (T[]) newData;
    }

    private class QueueIterator implements Iterator<T> {
        private final MaxBinaryHeap<T> pqCopy;

        public QueueIterator() {
            pqCopy = new MaxBinaryHeap<>(data, size);
        }

        @Override
        public boolean hasNext() {
            return !pqCopy.isEmpty();
        }

        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException("The queue is empty.");
            }
            return pqCopy.remove();
        }
    }

    private static void swap(Object[] array, int i, int j) {
        assert rangeCheck(array, i) && rangeCheck(array, j);

        if (i != j) {
            Object swap = array[i];
            array[i] = array[j];
            array[j] = swap;
        }
    }

    private static <T extends Comparable<? super T>>
            boolean less(T[] array, int i, int j) {
        assert rangeCheck(array, i) && rangeCheck(array, j);

        return array[i].compareTo(array[j]) < 0;
    }
    
    private static boolean rangeCheck(Object[] array, int i) {
        return array != null && i >= 0 && i < array.length;
    }
    
    /**
     * Calculates the floored logarithm base 2 of a given integer
     * in constant time using the bitwise operations.
     */
    private static int log2(int value) {
        int log = 0;
        // basically this algorithm counts the number of leading zeros,
        // but subtracted from the sizeof(int)

        // this covers the case when there are 1's on the left side
        // so the result is definitely greater than 16
        if ((value & 0xFFFF0000) != 0) {
            value >>>= 16;
            log += 16;
        }
        if ((value & 0xFF00) != 0) {
            value >>>= 8;
            log += 8;
        }
        if ((value & 0xF0) != 0) {
            value >>>= 4;
            log += 4;
        }
        if ((value & 0b1100) != 0) {
            value >>>= 2;
            log += 2;
        }
        if ((value & 0b10) != 0) {
            value >>>= 1;
            log += 1;
        }
        return log;
    }
    
    public static void main(String[] args) {
    	MaxBinaryHeap<Integer> heap = new MaxBinaryHeap<>();
    	Random random = new Random();
    	for (int i = 0; i < 10; i++) {
    		heap.offer(random.nextInt(100));
    	}
    	for (int i = 0; i < 10; i++) {
    		System.out.printf(" %d", heap.poll());
    	}
    }
}