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

import java.util.NoSuchElementException;

import static java.lang.Math.min;
import static java.lang.Math.max;

class MaxDaryHeap<T extends Comparable<? super T>>
        extends AbstractQueue<T> {
    private static final int MIN_HEIGHT = 1;
    
    // unlike the binary heap implementation this d-ary heap
    // does not add an additional null element on the 0-th place
    // in the array, thus, the greatest element of the queue is
    // stored in the data[0]
    private T[] data;
    private int size;
    // the arity of the heap (how many children does each node have)
    private final int d;
    
    /**
     * Create a d-ary heap with arity {@code d}.
     * @throws  IllegalArgumentException in case the arity {@code d} is
     *          less than 2.
     */
    @SuppressWarnings("unchecked")
    public MaxDaryHeap(int d) {
    	if (d < 2) {
    		throw new IllegalArgumentException(String.format("Expected: d >= 2."
    			+ " Got: d = %d.", d));
    	}
        this.d = d;
        // size = d^0 + d^1 + ... + d^h = (d^(h + 1) - 1) / (d - 1)
        int dataLength = pow(d, MIN_HEIGHT + 1) / (d - 1);
        data = (T[]) new Comparable<?>[dataLength];
        size = 0;
    }
    
    @SuppressWarnings("unchecked")
    private MaxDaryHeap(T[] data, int size, int d) {
        T[] copiedData = (T[]) new Comparable<?>[data.length];
        System.arraycopy(data, 0, copiedData, 0, data.length);
        this.data = copiedData;
        this.size = size;
        this.d = d;
    }
    
    /**
     * Inserts the specified value into the queue.
     * @throws  NullPointerException in case the {@code null} element
     *          is inserted.
     */
    @Override
    public boolean offer(T value) {
        if (value == null) {
            throw new NullPointerException(
                "Null elements are not allowed"
            );
        }
        grow(1);
        size++;
        data[size - 1] = value;
        swim(size - 1);
        return true;
    }
        
    @Override
    /**
     * Retrieves but does not remove the max element stored in the queue.
     */
    public T peek() {
        if (size == 0) {
            throw new NoSuchElementException("The heap is empty");
        }
        return data[0];
    }
    
    @Override
    /**
     * Retrieves and removes the max element stored in the queue.
     */
    public T poll() {
        if (size == 0) {
            throw new NoSuchElementException("The heap is empty");
        }
        T value = data[0];
        data[0] = null;
        size--;
        
        if (size > 0) {
            data[0] = data[size];
            sink(0);
        }
        
        // `true` for only a single element removed from the queue
        shrink(true);
        return value;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int size() {
        return size;
    }
    
    @Override
    public Iterator<T> iterator() {
        return new QueueIterator();
    }

    private void swim(int i) {
        assert i >= 0 && i < size;

        while (i > 0 && less(data, (i - 1) / d, i)) {
            swap(data, (i - 1) / d, i);
            i = (i - 1) / d;
        }
    }

    private void sink(int index) {
        assert index >= 0 && index < size;

        while (index * d + 1 < size) {
            int iMaxChild = index * d + 1;
            int upperBound = min(size, (index + 1) * d + 1);
            for (int i = 2; index * d + i < upperBound; i++) {
                if (less(data, iMaxChild, index * d + i)) {
                    iMaxChild = index * d + i;
                }
            }
            if (!less(data, index, iMaxChild)) {
                break;
            }
            swap(data, index, iMaxChild);
            index = iMaxChild;
        }
    }
    
    // the `by` argument could be useful if we'd implement a method
    // that adds several elements to the queue in a row, not just one
    private void grow(int by) {
        assert by > 0;

        if (size + by > data.length) {
            if (by == 1) {
                reallocate(data.length * d + 1);
            } else {
                reallocate(getFittingArraySize(size + by, d));
            }
        }
    }

    private void shrink(boolean oneElementRemoved) {
        if (size <= data.length / (d * d)) {
            int minSize = pow(d, MIN_HEIGHT + 1) / (d - 1);
            if (oneElementRemoved) {
                reallocate(max(data.length / d, minSize));
            } else {
                reallocate(max(getFittingArraySize(size, d), minSize));
            }
        }
    }
    
    @SuppressWarnings("unchecked")
    private void reallocate(int newSize) {
        assert newSize >= size;

        T[] newData = (T[]) new Comparable<?>[newSize];
        System.arraycopy(data, 0, newData, 0, size);
        data = newData;
    }

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

        public QueueIterator() {
            pqCopy = new MaxDaryHeap<>(data, size, d);
        }
        
        @Override
        public boolean hasNext() {
            return !pqCopy.isEmpty();
        }

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

    private static int getFittingArraySize(int size, int d) {
        // size + by = (d^(height + 1) - 1) / (d - 1)
        // => height = floor[log_d((size + by) * (d - 1))] - 1
        int height = log(d, size * (d - 1)) - 1;
        int arrayLength = (pow(d, height + 1) - 1) / (d - 1);
        return arrayLength;
    }

    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 void swap(Object[] array, int i, int j) {
        assert rangeCheck(array, i) && rangeCheck(array, j)
            : String.format("i = %d, j = %d, len(array) = %d",
            i, j, array.length);

        Object swap = array[i];
        array[i] = array[j];
        array[j] = swap;
    }

    private static boolean rangeCheck(Object[] array, int i) {
        return array != null && i >= 0 && i < array.length;
    }
    
    /**
     * Calculates the x^n value.
     */
    private static int pow(int x, int n) {
        assert n >= 0;

        int result = 1;
        for (int i = 0; i < n; i++) {
            result *= x;
        }
        return result;
    }
    
    /**
     * Calculates the floor(log_base(argument)) value.
     */
    private static int log(int base, int argument) {
        assert argument > 0 && base > 1;

        int log = 0;
        int intermediate = 1;
        while (intermediate <= argument) {
            intermediate *= base;
            log++;
        }
        return log;
    }

    public static void main(String[] args) {
        MaxDaryHeap<Integer> heap = new MaxDaryHeap<>(5);
    	Random random = new Random();
    	for (int i = 0; i < 100; i++) {
    		heap.offer(random.nextInt(10000));
    	}
    	for (int i = 0; i < 100; i++) {
    		System.out.printf(" %d", heap.poll());
    	}
    }
}