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 ]

Searching for a key in Log Files by connecting to Servers via SSH

This code helps us to search for the particular key in the log files by connecting to that servers and getting the entries that matches our search key. This can connect to different servers and fetch the results based on our confiuguration.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.InputStreamReader;
import java.io.Writer;

import ch.ethz.ssh2.Connection;
import ch.ethz.ssh2.Session;
import ch.ethz.ssh2.StreamGobbler;

/*
*
*Dependency : This java code is dependent on the below jar file which can be downloaded
*Jar Name : ganymed-ssh2-build210.jar
*
*/

public class FilePreviewer {

 private File outputFile;
 private Writer outputStream;
 public static String newline = System.getProperty("line.separator");
 
 public FilePreviewer()
 {
  
 }
 
 public FilePreviewer(String user, String pass)
 {
  
  String ipAd[]={"IP1","IP2"};
  int x=1, numOfServers=x+1;
  String keyText="searchKey"; //search key
  while(x<numOfServers) //incase if we want to search in more than one server in a loop
  {
   try
   {
    Connection connection = new Connection(ipAd[x]);
    connection.setTCPNoDelay(true);
    connection.connect();
    Authentication a=new Authentication(pass);
    System.out.println("Connection Established: "+ipAd[x]);
    outputFile=new File("output_"+x+".txt");//Output File name
    boolean flag=false;
    if(connection.isAuthMethodAvailable(user, "password"))
     flag = connection.authenticateWithPassword(user,pass);
    if(!flag)
    {
     flag = connection.authenticateWithKeyboardInteractive(user, a);
    }
    if (flag == true)
    {
     Session session = connection.openSession();
     String s3 = "grep -i '"+keyText+"' /home/userId/folder/filename.log"; //Configure the search command to point to any file. 
     session.execCommand(s3);
     StreamGobbler streamgobbler = new StreamGobbler(session.getStdout());
     BufferedReader bufferedreader = new BufferedReader(new InputStreamReader(streamgobbler));
     outputStream = new BufferedWriter(new FileWriter(outputFile));
     String cmdOut="";
     int count=0;
     do 
     {
      cmdOut = bufferedreader.readLine();
      if(cmdOut==null)
       break;
      System.out.println(cmdOut);
      outputStream.write(cmdOut+newline);
      count++;
     } while (true);
     outputStream.close();
     session.close();
     
     connection.close();
     if (count==0)
     {
      System.out.println("KeyText not found");
     }
     else
     {
      System.out.println("Found: "+count);
      count=0;
     }
    }
    else
    {
     System.out.println(" Authentication Failed");
    }
   }
   catch(Exception e)
   {
    System.out.println("n"+e.toString());
   }
   x=x+6;
  }
 }
 
 public static void main(String[] args) 
 {
  new FilePreviewer("user","pwd"); //user name and password
 }

}

//Code that takes care of KeyBoard Interactive Authentication

class Authentication implements ch.ethz.ssh2.InteractiveCallback
{
 int promptCount;
 String pwd;

 public Authentication(String password)
 {
  promptCount = 0;
  pwd = password;
 }

 public String[] replyToChallenge(String name, String instruction, int numPrompts, String prompt[], boolean echo[]) throws Exception
 {
  String result[] = new String[numPrompts];
  for(int i = 0; i < numPrompts; i++)
  {
   if(prompt[i].contains("Password:"))
   {
    result[i] = pwd;
    promptCount++;
   }
  }
  return result;
 }
}

[ Read More ]