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

Deleting a Node by passing data in LInkedList

Deleting a Node by passing data in LInkedList:-

The node can be deleted by passing the data value in a function.Here we have three pointers one to traverse the list other to point current node and third one to point previous of current node.



//deleting a given keypublic Node deleteKeyNode(Node head,int key){//traverse pointer Node temp=head;//previous pointer Node prevtemp=temp;while(temp!=null){//when key is at head positionif(key==head.data){ head=head.next; System.out.println("head is deleted");return head;}//when key is at any position other than headif(temp.data==key){ prevtemp.next=temp.next; temp.next=null; temp=prevtemp;} prevtemp=temp; temp=temp.next;}return head;}