MiniHeap

import java.util.ArrayList;
import java.util.PriorityQueue;

/*
 * author - PDT
 */
public class MinHeap {

    private double[] heap; //array of heap entries
    private int lastIndex; //index of last entry
    private static final int DEFAULT_INITIAL_CAPACITY = 25;

    public MinHeap() {
	this(DEFAULT_INITIAL_CAPACITY); //call next constructor
    }

    public MinHeap(int initialCapacity) {
	heap = new double[initialCapacity];
	lastIndex = 0;
    }

    /**
     * This method creates a heap from an array
     *
     * @param an array of double
     */
    public MinHeap(double arr[]) {
	heap = new double[arr.length * 2];
	for (int i = 0; i < arr.length; i++) {
	    heap[i + 1] = arr[i];
	}
	lastIndex = arr.length;
	initMinHeapFromArray();
    }

    /**
     * Heapify an array to create a heap
     */
    private void initMinHeapFromArray() {
	for (int i = lastIndex / 2; i >= 1; i--) {
	    int p = i;
	    while (hasChild(p) && ((p = reheap(p)) != -1)) {
	    }
	}
    }

    /**
     * Insert an new element at the end of the array and reheap up if neccessary
     *
     * @param new element
     */
    public void insert(double newEntry) {
	//Add the the end of the array
	heap[++lastIndex] = newEntry;
	int parentIndex = lastIndex / 2;

	//Reheap up the elelment
	while (hasChild(parentIndex) && (reheap(parentIndex) != -1)) {
	    parentIndex = parentIndex / 2;
	}
    }

    /**
     * Delete an element from the heap (having smallest value)
     *
     * @return the deleted element
     */
    public Double deleteMin() {
	double root = 0;
	if (!isEmpty()) {
	    //Put the element at the end array to the deleted position
	    root = heap[1];
	    heap[1] = heap[lastIndex--];

	    //Reheap down the root element
	    int rootIndex = 1;
	    while (hasChild(rootIndex) && ((rootIndex = reheap(rootIndex)) != -1)) {
	    }
	    return root;
	} else {
	    return null;
	}
    }

    /**
     * Check whether a node has any child
     *
     * @param the root index
     */
    public boolean hasChild(int rootIndex) {
	if (rootIndex * 2 <= lastIndex) {
	    return true;
	} else {
	    return false;
	}
    }

    /**
     * Reheap an element. Passing the element's index to reheap down, parent's index to reheap up
     *
     * @param the root index
     * @return the index of the element in which the root is reheaped down
     */
    public int reheap(int rootIndex) {
	//Get the index of left child
	int leftChildIndex = rootIndex * 2;

	if ((rootIndex * 2 + 1) <= lastIndex) {
	    //Get the index of right child after checking for its existence
	    int rightChildIndex = rootIndex * 2 + 1;

	    //Get the smaller child index
	    int smallerChildIndex;
	    if (heap[leftChildIndex] < heap[rightChildIndex]) {
		smallerChildIndex = leftChildIndex;
	    } else {
		smallerChildIndex = rightChildIndex;
	    }

	    //if the root is larger than the smaller child, swap their position
	    if (heap[rootIndex] > heap[smallerChildIndex]) {
		double temp = heap[rootIndex];
		heap[rootIndex] = heap[smallerChildIndex];
		heap[smallerChildIndex] = temp;

		//return the index of smaller child
		return smallerChildIndex;
	    } else {
		//The heap is in proper position, no operation needed
		return -1;
	    }
	} else {
	    //if the root is larger than the left child, swap their position
	    if (heap[rootIndex] > heap[leftChildIndex]) {
		double temp = heap[rootIndex];
		heap[rootIndex] = heap[leftChildIndex];
		heap[leftChildIndex] = temp;

		//return the index of left child (having smaller value)
		return leftChildIndex;
	    } else {
		//The heap is in proper position, no operation needed
		return -1;
	    }
	}
    }

    /**
     * This method allows users to decrease the value of an element at certain position
     *
     * @param the element position
     * @param the amount to decrease the node's key value
     */
    public void decreaseKey(int p, int delta) {
	heap[p] = heap[p] - delta;
	int parent = p / 2;

	//Reheap up the element
	while (hasChild(parent) && (reheap(parent) != -1)) {
	    parent = parent / 2;
	}
    }

    /**
     * This method allows users to increase the value of an element at certain position
     *
     * @param the element position
     * @param the amount to increase the node's key value
     */
    public void increaseKey(int p, int delta) {
	heap[p] = heap[p] + delta;

	//Reheap down the element
	while (hasChild(p) && ((p = reheap(p)) != -1)) {
	}
    }

    public double getMin() {
	return heap[1];
    }

    /**
     * Check whether the array is empty
     *
     * @return true if empty, false if not
     */
    public boolean isEmpty() {
	return lastIndex < 1;
    }

    /**
     * Get the number of elements in the array
     *
     * @return the size of the array
     */
    public int getSize() {
	return lastIndex;
    }

    public void clear() {
	heap = new double[DEFAULT_INITIAL_CAPACITY + 1];
    }

    @Override
    public String toString() {
	StringBuffer buffer = new StringBuffer();
	for (int i = 1; i <= lastIndex; i++) {
	    buffer.append(String.format("%.0f", heap[i]) + ", ");
	}
	return buffer.toString();
    }

    public static void main(String[] args) {
	double[] a = {13, 15, 10, 8, 7};
	ArrayList<Integer> arr = new ArrayList<>();
	arr.add(13);
	arr.add(15);
	arr.add(10);
	arr.add(8);
	arr.add(7);
	arr.add(30);
	PriorityQueue<Integer> queue = new PriorityQueue<>(arr);
	//System.out.println(queue);
	queue = new PriorityQueue<>();
	for (Integer b : arr) {
	    queue.add(b);
	}
	//System.out.println(queue);
	MinHeap minHeap = new MinHeap();
	minHeap.insert(13);
	minHeap.insert(15);
	minHeap.insert(10);
	minHeap.insert(8);
	minHeap.insert(7);
	minHeap.insert(30);

	System.out.println(minHeap.toString());
	minHeap.increaseKey(1, 10);
	minHeap.decreaseKey(6, 28);
	System.out.println(minHeap.toString());
	MinHeap minHeap1 = new MinHeap(a);
	System.out.println(minHeap1.toString());
	minHeap1.deleteMin();
	minHeap1.decreaseKey(2, 6);
	System.out.println(minHeap1.toString());
    }

}