INNOVATION: September 2015

Friday, 25 September 2015

MAX HEAP IN JAVA

There are two types of heap and one of that is Max heap.
In Max heap, we have to add element such that parent has maximum value than it’s child value.
Here we represent Max heap as binary tree and we are going to implement it with static array in which zero index has no value. We add value in array starting from index one as show in figure.
Here we have same concept of queue that FIFO(first in – first out)

Functionality :-

Enqueue – Add element at last.
Dequeue – Delete from first position.
Peek – Display First Element

Advantage of Max heap :- Sorting become more efficient.

Enqueue :-

Suppose if we want to add 25 in upper Max heap than we have to add 25 at index 11 (suppose index 11 is there.).But as we know Max heap means child has minimum value that it’s parent but here 7<25, which is not possible that we have to swap that two value for that what can do that Number[i/2]<->Number[i] means as we can here we have index 11 if take 11/2=5(in integer) than you can directly jump at it’s parent value and exchange that value.After exchanging that two value you will again find that 14<25 that again you can change that value with upper logic like this we have to move till we don’t find that Number[i/2]>Number[i].

Dequeue:-

As we know for for dequeue, we have remove element from root or from first position for that we have to move last element of array (here we have 1) at first position but still parent should have maximum value than child for that we have compare Number[i] with Number[2*i] and Number[2*i+1] because of you again go through upper image than you will that parent (Number[i]) has two child Number[2*i] and Number[2*i+1].So we have to compare that value and if you find and maximum value of child than parent that swap those two value.

Peek:-

In peek we have where first element of array or tree.

Algorithm Of Max heap

import java.util.Scanner;

class MaxPriorityQueue
{
 private int []Number;
 private int MAXI;
 private int size;
 
 public MaxPriorityQueue(){}
 
 public MaxPriorityQueue(int maxi)
 {
  size=0;
  MAXI=maxi;
  Number=new int[maxi+1];
 }
 
 public void Enqueue(int Item)
 {
  if(size<MAXI)
  {
   if(size==0)
   {
    size++;
    Number[size]=Item;
   }
   else
   {
    size++;
    if(Item<=Number[size/2])
    {
     Number[size]=Item;
    }
    else
    {
     int i=size;
     Number[i]=Item;
     while(true)
     {
      if(i==1){break;}
      if(Number[i]>Number[i/2])
      {
       int Temp=Number[i/2];
       Number[i/2]=Number[i];
       Number[i]=Temp;
       i=i/2;        
      }
      else
      {
       break;
      }
     }
    }     
   }   
  }
  else
  {
   System.out.println("\nMIN PRIORITY QUEUE IS FULL.\n");
  }
 }
 
 public int Dequeue()
 {
  if(size==0)
  {
   return -999;
  }
  else
  {
   int RemovedElement=Number[1];
   Number[1]=Number[size];
   size--;int i=1;
   
   while(true)
   {
    if(i>=size){break;}
    if(2*i+1<=size)
    {
     if(Number[2*i]>Number[i])
     {
      int Swapper=Number[i];
      Number[i]=Number[2*i];
      Number[2*i]=Swapper;
     }     
     if(Number[2*i+1]>Number[i])
     {
      int Swapper=Number[i];
      Number[i]=Number[2*i+1];
      Number[2*i+1]=Swapper;
     }
     i=i*2;
    }
    else if(2*i<=size)
    {
     if(Number[2*i]>Number[i])
     {
      int Swapper=Number[i];
      Number[i]=Number[2*i];
      Number[2*i]=Swapper;
      i=i*2;
     }
     else
     {
      break;
     }      
    }
    else
    {
     break;
    }
   }
   return RemovedElement;
  }
 }
 
 public void Display()
 {
  for(int i=1;i<=size;i++)
  {
   System.out.println(Number[i]);
  }
 }
 
 public int Peek()
 {
  if(size==0)
  {
   return -999;
  }
  else
  {
   return Number[1];   
  }
 }

}

class MaxPriority_Queue
{
 public static void main(String[] args)
 {
  MaxPriorityQueue m=new MaxPriorityQueue(10);
  m.Enqueue(40);
  m.Enqueue(5);
  m.Enqueue(10);
  m.Enqueue(30);
  m.Enqueue(1);
  m.Enqueue(15);
  m.Enqueue(25);
  m.Enqueue(50);
  m.Enqueue(27);
  m.Enqueue(45);
  
  m.Display();

System.out.println("\t\t\tSorted List");
  while(m.Peek()!=-999)
  {
   System.out.println("\t\t\t"+m.Dequeue());
   //m.Display();
  }     
 }
}

Download :- Max Heap

MIN HEAP USING JAVA

In Min heap, we have to add element such that parent has minimum value than it’s child value.

Here we represent Min heap as tree and we are going to implement it with static array in which zero index has no value. We add value in array starting from index one as show in figure.

Here we have same concept of queue that FIFO(first in – first out)

Functionality :-

Enqueue – Add element at last.

Dequeue – Delete from first position.

Peek – Display First Element

Advantage of Min heap:- Sorting become more efficient.

Enqueue :-

Suppose if we want to add 1 in upper Min heap than we have to add 1 at index 11 (suppose index 11 is there.).But as we know Min heap means child has maximum value that it’s parent but here 1<3, which is not possible that we have to swap that two value. For that what can do that Number[i/2]<->Number[i], means as we can here we have index 11 if take 11/2=5(in integer) than you can directly jump at it’s parent value and exchange that value. After exchanging that two value you will again find that 1<2 that again you can change that value with upper logic like this we have to move untill we don’t find that Number[i/2]>Number[i].

Dequeue:-

As we know for dequeue, we have to remove element from root or from first position for that we have to move last element of array (here we have 1) at first position but still parent should have minimum value than child for that we have compare Number[i] with Number[2i] and Number[2i+1] because of you again go through upper image than you will that parent (Number[i]) has two child Number[2i] and Number[2i+1].So we have to compare that value and if you find and minimum value of child than parent that swap those two value.

Peek:-

In peek we have where first element of array or tree.

Algorithm Of Min heap

import java.util.Scanner;

class MinPriorityQueue
{
 private int []Number;///Array to store data
 private int MAXI;//Maximum size of static array
 private int size;//number of element in list

public MinPriorityQueue(){}//construtor
 
 public MinPriorityQueue(int maxi)//parameterized construtor
 {
  size=0;
  MAXI=maxi;
  Number=new int[maxi+1];
 }
 
 public void Enqueue(int Item)//Add element in min priority queue
 {
  if(size<MAXI)
  {
   if(size==0)
   {
    size++;
    Number[size]=Item;
   }
   else
   {
    size++;
    if(Item>=Number[size/2])
    {
     Number[size]=Item;
    }
    else
    {
     int i=size;
     Number[i]=Item;
     while(true)
     {
      if(i==1){break;}
      if(Number[i]<Number[i/2])
      {
       int Temp=Number[i/2];
       Number[i/2]=Number[i];
       Number[i]=Temp;
       i=i/2;        
      }
      else
      {
       break;
      }
     }
    }     
   }   
  }
  else
  {
   System.out.println("\nMIN PRIORITY QUEUE IS FULL.\n");
  }
 }
 
 public int Dequeue()//delete root or first element
 {
  if(size==0)
  {
   return -999;
  }
  else
  {
   int RemovedElement=Number[1];
   Number[1]=Number[size];
   size--;int i=1;
   
   while(true)
   {
    if(i>=size){break;}
    if(2*i+1<=size)
    {
     if(Number[2*i]<Number[i])
     {
      int Swapper=Number[i];
      Number[i]=Number[2*i];
      Number[2*i]=Swapper;
     }     
     if(Number[2*i+1]<Number[i])
     {
      int Swapper=Number[i];
      Number[i]=Number[2*i+1];
      Number[2*i+1]=Swapper;           
     }
     i=i*2;
    }
    else if(2*i<=size)
    {
     if(Number[2*i]<Number[i])
     {
      int Swapper=Number[i];
      Number[i]=Number[2*i];
      Number[2*i]=Swapper;
      i=i*2;
     }
     else
     {
      break;
     }      
    }
    else
    {
     break;
    }
   }
   return RemovedElement;   
  }
 }
 
 public int Peek()//display first value of array
 {
  if(size==0)
  {
   return -999;
  }
  else
  {
   return Number[1];   
  }
 }
 
 public void Display()
 {
  for(int i=1;i<=size;i++)
  {
   System.out.println(Number[i]);
  }
 }
}

class MinPriority_Queue
{
 public static void main(String[] args)
 {
  MinPriorityQueue m=new MinPriorityQueue(10);
  m.Enqueue(6);
  m.Enqueue(2);
  m.Enqueue(10);
  m.Enqueue(3);
  m.Enqueue(9);
  m.Enqueue(15);
  m.Enqueue(74);
  m.Enqueue(4);
  m.Enqueue(65);
  m.Enqueue(45);
  m.Display(); 
  System.out.println("\nDeleted Element :- "+m.Dequeue());
  m.Display();

System.out.println("\t\t\tSorted List");
  while(m.Peek()!=-999)
  {
   System.out.println("\t\t\t"+m.Dequeue());
  }   
 }
}

Download :- Min Heap

Sunday, 20 September 2015

Algorithm For Findind LU Factorization of Given Matrix in Java

Algorithm For Finding LU Factorization of Given Matrix in Java

Here given matrix can be decompose into two part L and U.
Here I have Algorithm for solving LU Factorization for given matrix.
You have to keep in mind that L part of given m * n matrix has dimension of m * m where as U part has dimension of m * n.

import java.util.Scanner;

public class Matrix {
    
    private int Row; //NO OF ROWS
    private int Column; //NO OF COLUMNS
    private float [][]Elements;//FOR CARRING ELEMENTS
    private float [][]U; //FOR LU FACTORIZATION
    private float [][]L; //
    private float []T;
    private int count;//FOR CHECKING EXISTS OF LU FACTORIZATION.
    private boolean write;//FOR CHECKING METRIX EXISTANCES.
    public Matrix(int No_Row,int No_Column)//PARAMETERIZED CONSTRUCTOR
    {
        if(No_Row>0 && No_Column>0)
        {
            count=0;Determinat=0;
            write=true;
            Row=No_Row;
            Column=No_Column;
            Elements = new float[No_Row][No_Column];
                U=new float[No_Row][No_Column];
                L=new float[No_Row][No_Row];
           
            T=new float[No_Column];
            for(int i=0;i<No_Column;i++){T[i]=1;}

}
        else
        {
            write=false;
            System.out.println("\nYOU CAN NOT MAKE MATRIX WITH THIS DIMENTIONS.\n");
        }
    }

public void SET_ELEMENTS_OF_MATRIX()
    {
        //if(!write){return ;}
        Scanner x=new Scanner(System.in);

for(int i=0;i<Row;i++)
        {
            for(int j=0;j<Column;j++)
            {
                System.out.println("ENTER ["+i+"]["+j+"] ELEMENT OF MATRIX :- ");
                Elements[i][j]=x.nextFloat();
            }
        }

int Hold;
        for(int i=0;i<Row;i++)
        {
            for(int j=0;j<Row;j++)
            {
                if(i<j || i>j){L[i][j]=0;}
                else
                {
                    L[i][j]=1;
                }     
            }
        }
        Algorithms_of_EF();
    }
    
    private void Algorithms_of_EF()
    {
        //if(!write){return;}
        int R=0;int CC=-1;int RC=-1;
        for(int i=0;i<Column;i++)
        {
            if(R<Row)
            {  
                if(Elements[R][i]!=0)
                {
                    CC++;
                    RC=CC;
                    if(RC<row && CC<Row)
                    {
                        L[RC][CC]=Elements[R][i];T[CC]=Elements[R][i];
                    }
                                      
                    for(int k=R+1;k<Row;k++)
                    {
                        float []Array=new float[Column];
                            RC++;
                            if(RC<Row && CC<Row){L[RC][CC]=Elements[k][i];}

for(int l=0;l<Column;l++)
                        {
                            Array[l]=Elements[k][l] - ((Elements[R][l]*Elements[k][i])/Elements[R][i]);
                        }
                        for(int l=0;l<Column;l++)
                        {
                            Elements[k][l]=Array[l];
                        }
                    }
                    R++; 
                }
                else
                {
                    int Temp=-1;
                    for(int j=(Row-1);j>R;j--)
                    {
                        if(Elements[j][i]!=0)
                        {
                                Temp=j;
                                break;
                        }
                    }

if(Temp!=-1)
                    {
                        count++;
                        for(int f=0;f<Column;f++)
                        {
                            float Temp1= Elements[Temp][f];
                            Elements[Temp][f]=Elements[R][f];
                            Elements[R][f]=Temp1;
                        }

CC++; 
                        RC=CC;
                        if(RC<row && CC<Row){L[RC][CC]=Elements[R][i];T[CC]=Elements[R][i];}

for(int k=R+1;k<Row;k++)
                        {
                            float []Array=new float[Column];

RC++;
                            if(RC<Row && CC<Row)
                            {
                               L[RC][CC]=Elements[k][i];
                            }

for(int i=0;i<Row;i++)
        {
            for(int j=0;j<Column;j++)
            {
                    U[i][j]=Elements[i][j];
            }
        }
    }

private void Set_L_Part()
    {
        //int Temp;
        for(int i=0;i<Row;i++)
        {
            for(int j=0;j<Row;j++)
            {
                L[j][i]=L[j][i]/T[i];
            }
        }  
    }

public void Get_LU_FACTORIZATION_Part()
    {
        
        if(count==0)
        {
            Set_L_Part();

System.out.println("\n------ L PART ------\n");
            int Temp;
            for(int i=0;i<Row;i++)
            {
                for(int j=0;j<Row;j++)
                {
                        if(L[i][j]==(-0.0)){L[i][j]=0;}
                        System.out.print(L[i][j]+"  ");
                }
                System.out.println();
            }

System.out.println("\n------ U PART ------\n");
                int Temp1;
                for(int i=0;i<Row;i++)
                {
                    for(int j=0;j<Column;j++)
                    {
                            System.out.print(U[i][j]+"      ");
                    }
                    System.out.println();
                }
        }
        else
        {
            System.out.println("\nLU FACTORIZATION IS NOT POSSIBLE THIS MATRIX.\n");
        }
    }
    
    public void Display()
    {
        
        System.out.println("\n\n");
        for(int i=0;i<Row;i++)
        {
            for(int j=0;j<Column;j++)
            {
                if(Elements[i][j]==(-0.0)){Elements[i][j]=0;}
                System.out.print(Elements[i][j]+"  ");
            }
            System.out.println();
        }
    }
}

Friday, 25 September 2015

MAX HEAP IN JAVA

MIN HEAP USING JAVA

Sunday, 20 September 2015

Algorithm For Findind LU Factorization of Given Matrix in Java

Main Class