MergeSort - Java Program

public int[] mergeSort(int[] arr,int start,int end)
{
int mid=(start+end)/2;

if(start {
mergeSort(arr,start,mid);
mergeSort(arr,mid+1,end);
merge(arr,start,mid,end);
}

return arr;
}

//To merge two sorted portions of an array
public int[] merge(int[]arr,int low,int mid,int end)
{
int[] temp=new int[end-low+1];

int ptr1=low,ptr2=mid+1,ptr3=0;

//Copy the elements in sorted order to a third array - O(n)
while(ptr1<=mid && ptr2<=end )
{
if(arr[ptr1] {
temp[ptr3]=arr[ptr1];
ptr1++;
ptr3++;
}
else if(arr[ptr2]<=arr[ptr1] && ptr2<=end )
{
temp[ptr3]=arr[ptr2];
ptr2++;
ptr3++;
}
}

//Copy remaining elements from first half
while(ptr1<=mid)
{ temp[ptr3]=arr[ptr1];
ptr1++;
ptr3++;
}

//Copy remaining elements from second half
while(ptr2<=end)
{ temp[ptr3]=arr[ptr2];
ptr2++;
ptr3++;
}


//Copy the sorted temp array back to the main array -O(n)
for(int i=low,j=0;i<=end;i++)
arr[i]=temp[j++];


return arr;
}

Java program to implement QuickSort

Java program to find the middle of a linked list in O(n) time

Method:
. Use two pointers in a loop
. One pointer will jump one node, where as the other pointer will jump 2 nodes.
. When the fast pointer reaches the end, the slow pointer will be at the middle.

To find if a linked list has a loop

Problem: Suppose the last node in the linked list point back to any of the previous nodes, creating a loop. How will you detect this?


Use 2 pointers that traverses the list with different speed. For example, at each step, pointer1 will jump one node and pointer2 will jump 2 nodes.

Start both pointers from head.

ptr1=head.next;
ptr2=head.next.next;


Now that ptr2 has already marched ahead of ptr1, there's no chance these two pointers will point to the same node, unless there's a loop.


      

To find the intersection of two linked list

1) Get count of the nodes in first list, let count be c1.
2) Get count of the nodes in second list, let count be c2.
3) Get the difference of counts d = abs(c1 – c2)
4) Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.
5) Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)

Java Program to implement Min Heap

package lab.heaps;

public class MinHeap
{
  int MAX_SIZE=100;
  int last_position; //last position which is empty
  Comparable[] heap=new Comparable[MAX_SIZE];
  //left child:2n+1, Right child: 2n+2
 
  public MinHeap()
  {
 last_position=0;
  }
 
  public void insert(Object o)
  {
    Comparable data=(Comparable)o;
    Comparable temp;
    int i=last_position;
    last_position++;
    heap[i]=data;
    int parent_i=getParentPosition(i);
  
    if(parent_i==-1)
    { // No more checks needed for first insertion, so return
     return;
    }
  
    while(heap[parent_i].compareTo(heap[i])>0)
    {
     temp=heap[i];
     heap[i]=heap[parent_i];
     heap[parent_i]=temp;
     i=parent_i;
     parent_i=getParentPosition(i);
     if(parent_i==-1)
        {//To avoid array out of bound exception
         return;
        }
    
    }
  
   }
 
  public Object deleteMin()
  {
 Object temp1=heap[0];
 Comparable temp;

 if(last_position==0)
 {
 return null;
 }
 else if(last_position==1)
 {
     heap[0]=null;
     return temp1;
 }

 int i=last_position-1;
 heap[0]=heap[i];
 heap[i]=null;
 i=0;

// If there exists a smaller child for i, then get it.
 int next=getSmallerChild(i);

 while(next!=-1)
 {  
// Go down the heap until you have no smaller child
 temp=heap[i];
 heap[i]=heap[next];
 heap[next]=temp;
 i=next;
 next=getSmallerChild(i);
 }

 last_position--;
 return temp1;
 
  }
 
  public Object getMin()
  {
 return heap[0];
  }
 
  public int getLeftChildPosition(int i)
  {
  return (2*i)+1;
  }
 
  public int getRightChildPosition(int i)
  {
  return (2*i)+2;
  }

  public int getParentPosition(int i)
  {
 if(i==0)
 {
 return -1;
 }
 else if(i%2!=0)
 {
 return (i/2);
 }
 else
 {
 return (i/2)-1;
 }
 
  }
 
  public int getSmallerChild(int i)
  {
//Returns the index of the smaller child, if any of the children are smaller
int left=getLeftChildPosition(i);
int right=getRightChildPosition(i);

if(heap[left]==null && heap[right]==null)
{
return -1;
}
else if(heap[left]!=null && heap[right]==null)
{
if(heap[left].compareTo(heap[i])<0)
   return left;
else
return -1;
}
else if(heap[left]!=null && heap[right]!=null)
{
if(heap[left].compareTo(heap[right])<0 && heap[left].compareTo(heap[i])<0)
{
return left;
}
else if(heap[left].compareTo(heap[right])>0 && heap[right].compareTo(heap[i])<0)
{
return right;
}
else
{
return -1;
}
}

return -1;

  }


}