Java program to create a Binary Heap and Perform various operation

A binary heap (min-heap) is a complete binary tree with elements from a partially ordered set, such that the element at every node is less than (or equal to) the the element at it's left and right child.

This Binary Heap is a min-heap implemented with one-based array (root is element 1; children of element n are elements 2n and 2n+1) for simplicity.

Complexity: Space O(n), findMin O(1), insert O(logn), deleteMin O(logn), buildHeap O(n);

class BinaryHeap {

 private int nodes[];
 private int size;
 private int capacity;
 

 public BinaryHeap(int capacity) {
  this.size = 0;
  this.capacity = capacity;
  this.nodes = new int[capacity + 1];
 }

 public int size() {
  return size;
 }

 public int findMin() {
  if (size <= 0) {
   throw new RuntimeException("Empty Heap is empty.");
  }
  return nodes[1];
 }

 public void insert(int e) {
  if (size >= capacity) {
   throw new RuntimeException("Heap overflow.");
  }

  size++;
  nodes[size] = e;
  percolateUp();
 }

 public int deleteMin() {
  if (size <= 0) {
   throw new RuntimeException("Empty Heap is empty.");
  }
  int min = findMin();
  nodes[1] = nodes[size];
  size--;
  percolateDown();
  return min;
 }

 private void percolateDown() {
  int index = 1;
  while (true) {
   int child = index * 2;
   if (child > size)
    break;
   if (child + 1 <= size) {
    // if there are two children -> take the smallest or
    // if they are equal take the left one
    child = findMin(child, child + 1);
   }
   if (nodes[index] <= nodes[child])
    break;
   swap(index, child);
   index = child;
  }
 }

 private void percolateUp() {
  int index = size();
  while (index > 1) {
   int parent = index / 2;
   if (nodes[index] >= nodes[parent])
    break;
   swap(index, parent);
   index = parent;
  }
 }

 private void swap(int i, int j) {
  int temp = nodes[i];
  nodes[i] = nodes[j];
  nodes[j] = temp;
 }

 private int findMin(int leftChild, int rightChild) {
  if (nodes[leftChild] <= nodes[rightChild]) {
   return leftChild;
  } else {
   return rightChild;
  }
 }
 
 public static void main(String[] args) {
  BinaryHeap bh = new BinaryHeap(10);
  bh.insert(7);
  bh.insert(5);
  bh.insert(9);
  bh.insert(6);
  bh.insert(4);
  bh.insert(8);
  bh.insert(10);
  bh.insert(1);
  bh.insert(3);
  bh.insert(2);
  
  System.out.println("Size of Binary Heap is : " + bh.size());

  System.out.println("Delete min from Binary Heap : " + bh.deleteMin());
  System.out.println("Size of Binary Heap is : " + bh.size());

  System.out.println("Delete min from Binary Heap : " + bh.deleteMin());
  System.out.println("Size of Binary Heap is : " + bh.size());
 }
 
}

Output of this Program

Size of Binary Heap is : 10
Delete min from Binary Heap : 1
Size of Binary Heap is : 9
Delete min from Binary Heap : 2
Size of Binary Heap is : 8

Try this by Yourself : http://ideone.com/FnSiPv

[ Read More ]

Create an Adjacency matrix Graph and perform Add and Remove operation

import java.util.ArrayList;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * Implementation of a directed unweighted Graph using Adjacency Matrix
 * 
 * Complexity: addEdge, removeEdge, hasEdge O(1) / outEdges, inEdges O(n) /
 * Space O(n^2)
 */
public class AdjMatrixGraph {
 int size;
 private boolean[][] matrix;
 public static final byte WHITE = 1;
 public static final byte GREY = 2;

 public AdjMatrixGraph(int size) {
  this.size = size;
  this.matrix = new boolean[size][size];
 }

 public void addEdge(int nodeA, int nodeB) {
  matrix[nodeA][nodeB] = true;
 }

 public void removeEdge(int nodeA, int nodeB) {
  matrix[nodeA][nodeB] = false;
 }

 public boolean hasEdge(int nodeA, int nodeB) {
  return matrix[nodeA][nodeB];
 }

 public List<Integer> outEdges(int i) {
  List<Integer> edges = new ArrayList<Integer>();
  for (int j = 0; j < size; j++) {
   if (matrix[i][j]) {
    edges.add(j);
   }
  }
  return edges;
 }

 public List<Integer> inEdges(int i) {
  List<Integer> edges = new ArrayList<Integer>();
  for (int j = 0; j < size; j++) {
   if (matrix[j][i]) {
    edges.add(j);
   }
  }
  return edges;
 }

 public int nVertices() {
  return size;
 }

 public void breadthFirstSearch(int root) {
  boolean[] seen = new boolean[nVertices()];
  Queue<Integer> q = new LinkedList<Integer>();
  q.add(root);
  seen[root] = true;
  while (!q.isEmpty()) {
   int i = q.remove();
   for (Integer j : outEdges(i)) {
    if (!seen[j]) {
     q.add(j);
     seen[j] = true;
    }
   }
  }
 }

 public void depthFirstSearch(int r) {
  byte[] c = new byte[nVertices()];
  Stack<Integer> s = new Stack<Integer>();
  s.push(r);
  while (!s.isEmpty()) {
   int i = s.pop();
   if (c[i] == WHITE) {
    c[i] = GREY;
    for (int j : outEdges(i))
     s.push(j);
   }
  }
 }

 public static void main(String[] args) {
  AdjMatrixGraph graph = new AdjMatrixGraph(10);

  graph.addEdge(1, 3);
  graph.addEdge(2, 4);
  graph.addEdge(6, 8);
  graph.addEdge(3, 2);

  System.out.println("Edge from 6 to 8 is : " + graph.hasEdge(6, 8));
  System.out.println("Edge from 2 to 4 is : " + graph.hasEdge(2, 4));
  System.out.println("Edge from 3 to 2 is : " + graph.hasEdge(3, 2));
  System.out.println("Edge from 1 to 3 is : " + graph.hasEdge(1, 3));

  graph.removeEdge(6, 8);
  System.out.println("Edge from 6 to 8 is : " + graph.hasEdge(6, 8));

 }
}

Output of this Program:

Edge from 6 to 8 is : true
Edge from 2 to 4 is : true
Edge from 3 to 2 is : true
Edge from 1 to 3 is : true
Edge from 6 to 8 is : false

Try this by Yourself : http://ideone.com/ZZm7rW

[ Read More ]

To Sort an Interger Array using Shell Sort

To Sort an Interger Array using Shell Sort

class ShellSort {

    public static int[] shellSort(int[] array) {
  int N = array.length;
  
  // determine the initial h value
  int h = 1;
     while (h < N / 3) 
      h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
     
     while (h >= 1) {
      // h-sort the array
      for (int i = h; i < array.length; i++) {
       // do insertion sort for h-sized array
       for (int j = i; j >= h && array[j] < array[j - h]; j -= h)
        swap(array, j, j - h);
      }
      
      h = h / 3; // reverse the h-size
     }
     
     return array;
 }
 
 /*
  * swaps data elements between 2 indexes of an array
  */
 private static void swap(int[] array, int i, int j) {
  int temp = array[i];
  array[i] = array[j];
  array[j] = temp;
 } 
    
    public static void  main(String args[]){
     ShellSort sSort = new ShellSort();
     int[] array = { 77, 99, 44, 55, 22, 88, 11, 0, 66, 33 };
     int[] sortedArray = sSort.shellSort(array);
     for (int i = 0; i < array.length; i++)
         System.out.println(sortedArray[i]);
     
    }
}

Output of the Program : 

0
11
22
33
44
55
66
77
88
99

Try it by yourself here : http://ideone.com/veRv5P

[ Read More ]

Sort an Integer array with Bucket Sort

Here is a java program to Sort an Integer array with Bucket Sort

class BucketSort {

    public int[] bucketSort(int[] array) {
        // create an array the size of the largest value + 1
        int[] bucket = new int[100];   

        // for every value in array, increment its corresponding bucket
        for (int i = 0; i < array.length; i++)
            bucket[array[i]]++;

        int outPos = 0;
        for (int i = 0; i < bucket.length; i++) { 
         if (bucket[i] > 0)
             array[outPos++] = i;
        }
        
        return array;
    }
    
    public static void  main(String args[]){
     BucketSort bSort = new BucketSort();
     int[] array = { 77, 99, 44, 55, 22, 88, 11, 0, 66, 33 };
     int[] sortedArray = bSort.bucketSort(array);
     for (int i = 0; i < array.length; i++)
         System.out.println(sortedArray[i]);
     
    }
}

Output of the Program :

0
11
22
33
44
55
66

Try By Yourself Here : http://ideone.com/OpHXmH

[ Read More ]