Skip to main content

Heap implementation in JAVA

In this tutorial we will see all the functionalities of heaps implemented through java language.



package com.problems.heap;



public class HeapFunctions {
  
 //Function to generate maxheapify where root is max than childs
 public void maxHeapify(int Arr[],int i,int N)
 {
    int largest;
    int left = 2*i+1;     //left child
       int right = 2*i +2;  //right child
       
       System.out.println("left"+" "+left);
       System.out.println("right"+" "+right);
       System.out.println("Max size"+" "+N);
       if(left< N && Arr[left] > Arr[i] )
       {
       largest = left;
       System.out.println("largest left"+largest);
       }
       else
       {
            largest = i;
            System.out.println("largest i"+largest);
       }
       if(right < N && Arr[right] > Arr[largest] )
       {
       largest = right;
       System.out.println("largest right"+largest);
       }
       if(largest != i )
       {
        System.out.println("No largest"+largest);
           Arr=swap (Arr, i , largest);
           maxHeapify (Arr,largest,N);
       } 
 }
 
 //function to generate minheapify where root is minimum than childs
 public void minHeapify(int Arr[],int i,int N)
 {
    int smallest;
    int left = 2*i+1;     //left child
       int right = 2*i +2;  //right child
       
       if(left< N && Arr[left]<  Arr[i] )
       {
       smallest = left;
       System.out.println("smallest left"+smallest);
       }
       else
       {
        smallest = i;
            System.out.println("smallest i"+smallest);
       }
       if(right < N && Arr[right] < Arr[smallest] )
       {
        smallest = right;
       System.out.println("smallest right"+smallest);
       }
       if(smallest != i )
       {
        System.out.println("No largest"+smallest);
           Arr=swap (Arr, i , smallest);
           minHeapify (Arr,smallest,N);
       } 
 }
 
 //function to swap elements in an Array
 public int[] swap(int Arr[],int x,int y)
 {
  System.out.println("in swap");
  System.out.println("x"+x+"y"+y);
  int temp=Arr[x];
  Arr[x]=Arr[y];
  Arr[y]=temp;
  return Arr;
 }
 
 //function to build maximum heap
 void build_maxheap (int Arr[ ],int N)
 {
     for(int i =N/2; i >= 0 ; i-- )
     {
         maxHeapify (Arr, i,N) ;
     }
 }
 
 //function to build minimum heap
 void build_minheap (int Arr[ ],int N)
 {
     for(int i =N/2; i >= 0 ; i-- )
     {
         minHeapify (Arr, i,N) ;
     }
 }
 
 
 //heap sorting 
 void heap_sort(int Arr[ ],int N)
 {
     int heap_size = N;
    
     for(int i = N-1; i>=1 ; i-- )
     {
      build_maxheap(Arr,heap_size);
      System.out.println("this"+i);
      System.out.println("i="+i+"");
         Arr=swap(Arr,0, i);
         heap_size = heap_size-1;
         System.out.println("calling max heapify"+heap_size);
        
     }
 }
 
 
 
}


Driver program to run:-


package com.problems.heap;

public class HeapOperations {


 
 public static void main(String[] args)
 {
  int Elem[]={4,3,7,1,8,5};
 HeapFunctions func=new HeapFunctions();
 //max heapify
 func.maxHeapify(Elem, 6, Elem.length);
 System.out.println("min heap");
 func.build_maxheap(Elem, Elem.length);
 System.out.println("");
 for(int i=0;i<Elem.length;i++)
 {

  System.out.print(Elem[i]+",");
 
 }
 System.out.println("");
 //
 
 //min heapify
 System.out.println("min heap");
 func.build_minheap(Elem, Elem.length);
 System.out.println("");
 for(int i=0;i<Elem.length;i++)
 {
  
  System.out.print(Elem[i]+",");
  
 }
 System.out.println("");
 //
 
 //heap sort
 System.out.println("Heap Sort length"+ Elem.length);
 int Elemm[]={4,3,7,1,8,5};
 
 func.heap_sort(Elemm, Elemm.length);
 
 System.out.println("");
 System.out.println("sorted array");
 for(int i=0;i<Elemm.length;i++)
 {
  
  System.out.print(Elemm[i]+",");
  
 }
 
 //
 }
}

Comments

  1. import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Arrays;


    public class heap1 {
    public static void main(String[] args) throws IOException {
    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(bufferedReader.readLine().trim());
    Heap heap = new Heap(N);
    for(int i = 0; i < N; i++){
    String[] strings = bufferedReader.readLine().split("\\s+");
    int operation = Integer.parseInt(strings[0]);
    switch (operation){
    case 1: int val = Integer.parseInt(strings[1]);
    heap.insert(val);
    break;
    case 2: int value = Integer.parseInt(strings[1]);
    heap.delete(value);
    break;
    case 3:heap.printMin();
    }
    }
    }
    }

    class Heap {
    int[] array;
    int curIndex = 0;

    Heap(int N){
    array = new int[N];
    Arrays.fill(array, Integer.MAX_VALUE);
    }

    int getParent(int index){
    return index/2;
    }

    int leftChild(int index){
    return 2 * index;
    }

    int rightChild(int index){
    return 2*index + 1;
    }

    boolean isLeaf(int index){
    if(index >= (curIndex /2) && index <= curIndex){
    return true;
    }
    return false;
    }

    void swap(int fromIndex, int toIndex){
    int temp = array[fromIndex];
    array[fromIndex] = array[toIndex];
    array[toIndex] = temp;
    }

    void insert(int element){
    array[++curIndex] = element;
    int idx = curIndex;
    while (idx > 1 && array[idx] < array[getParent(idx)]){
    swap(idx, getParent(idx));
    idx = getParent(idx);
    }
    }

    void printMin(){
    if(curIndex > 0){
    System.out.println(array[1]);
    }
    }

    void heapify(int index){
    if(!isLeaf(index)){
    int leftChildIndex = leftChild(index);
    int rightChildIndex = rightChild(index);
    int leftChild = array[leftChildIndex];
    int rightChild = array[rightChildIndex];
    int item = array[index];
    if(leftChild < rightChild){
    if(leftChild < item){
    swap(leftChildIndex, index);
    heapify(leftChildIndex);
    }
    }
    else {
    if(rightChild < item) {
    swap(rightChildIndex, index);
    heapify(rightChildIndex);
    }
    }
    }
    }

    void delete(int item){
    int pos = -1;
    for(int i = 1; i <= curIndex; i++){
    if(array[i] == item){
    pos = i;
    break;
    }
    }

    for(int j = pos; j < curIndex; j++){
    array[j] = array[j+1];
    }
    array[curIndex] = Integer.MAX_VALUE;
    curIndex--;

    if(curIndex > 0)
    heapify(1);
    }
    }

    ReplyDelete

Post a comment

.

Popular posts from this blog

Driver program to perform operations in graph

Driver program to perform operations in graph:-



package com.problems.graph;publicclassGraphDriver{publicstaticvoidmain(String[] args){ BFSGraph g=new BFSGraph(); g.addVertex('A'); g.addVertex('B'); g.addVertex('C'); g.addVertex('D'); g.addVertex('E'); g.addVertex('F'); g.addVertex('G'); g.addVertex('H'); g.addEdge(0,1); g.addEdge(1,2); g.addEdge(1,7); g.addEdge(2,3); g.addEdge(2,4); g.addEdge(7,4); g.addEdge(4,5); g.addEdge(4,6); g.bfs();}}

WHAT DOES LOAD BALANCER DO BETWEEN CLIENT COMPUTER AND SERVERS?

Whenever we talk about websites we often tend to be restricted to the domain and hosting only. A person who is generally developing websites does only take care of designing the front end and moreover functionality related to back-end. Most of the  people never thought about the servers and load balancer. Even a student in computer science often confused about the true working of traffic management in servers as well as load balancing it to make sure running the website and application without causing any issue to the end users.
So this article is all about how actually the load balancer work in a real time environment. There are three things that need to understand
1.Client 2.Load balancer 3.Server
Server -Servers are computer programs running to serve the requests of other programs, the clients Thus, the server performs some tasks on behalf of clients. It facilitates the clients to share data, information or any hardware and software resources
The client is the end user who is using …