BinaryHeap.java

package com.datastructures;

public class BinaryHeap {
  //This is an implementation of Binary Heap using an array.
	//The Binary Heap is represented as a Tree. The Root of the tree is the 1st index in the array. Lets call that 'k'.
	//The left and right child of the tree are computed using the formula 2k and 2k+1
	//If you want to find the index of the parent from, from the node you're currently in, then you can use the formula k/2.
	//This is how we shall be traversing the tree and also this is the reason we keep the root of the tree at the 1st index of the array and not the 0th.
	//Property of the Binary Heap Tree: The element in the root always has to be greater than both its children/child elements
	
	//Later you can implement a resizable array logic.
	int[] bH;
	
	public BinaryHeap(int N)
	{
		bH = new int[N + 1];
	}
	
	//Index of the root
	int k = 1;
	
	//The APIs
	public void put(int key)
	{
		//Place the element at the end of the array
		bH[this.k] = key;		
		if(bH[this.k] > bH[this.k/2])
		{
			//since the elements in an array implementation of the binary heap is put at the end of the array,
			//we must always check if the property of the tree holds true or not.
			swim(this.k);
		}
		this.k++;
	}
	
	public void deleteMax()
	{
		//Replace the element in the root with the element at the end of the array
		bH[1] = bH[k];
		//Restore the order of the tree
		sink(1);
		this.k--;
	}
	
	public void deleteMin()
	{
		bH[this.k - 1] = 0;
		this.k--;
	}

	public void swim(int k)
	{
		while((k != 1) && (bH[k] > bH[k/2]))
		{
			swap(k, k/2);
			k = k/2;
		}
	}

	public void sink(int k)
	{
		while(2*k <= this.k)
		{
			int j = 2*k;
			if(max(j, j+1)) j++;
			if(bH[k] < bH[j])
				swap(k, j);
			else if(bH[k] > bH[j]) 
				break;
			k = j;
		}
	}

	private boolean max(int i, int j) {
		if(bH[i] < bH[j])
			return true;
		return false;
	}

	private void swap(int i, int j) {
		int temp = 0;
		temp = bH[i];
		bH[i] = bH[j];
		bH[j] = temp;
	}
	
	private void printAll() {
		for(int i=1; i < this.k; i++)
		{
			System.out.print(bH[i] + " ");
		}		
		System.out.println();
	}
	
	public static void main(String[] args) throws Exception
	{
		int a[] = {6,5,7,8,2,9,8,1};
		BinaryHeap bh = new BinaryHeap(a.length);
		for(int i=0; i < a.length; i++)
		{
			bh.put(a[i]);
		}
		
		System.out.println("Elements in Binary Heap: ");
		bh.printAll();
		
		System.out.println("Deleting Minimum: ");
		bh.deleteMin();
		bh.printAll();
		
		System.out.println("Deleting Maximum: ");
		bh.deleteMax();
		bh.printAll();
	}
}

This is again a practice program that I have written to revise my knowledge on Algorithms.