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

Bubble Sort in JAVA

What is bubble sort?

It is a sorting technique that is based on the comparison.Here we compare adjacent element, if the first element is larger than the second we swap each other. We do the same procedure again and again until array do not sort completely.

Example:-
5 1 4 2 8



51428here pass is nothing but iterating the loops equal to number of elements in the array but if it already sorted before then we can break the loop anddo existPASS1 case0 1 //check 0 and first element15428 case1 2 //check 1 and 2 element14528 case2 314258 case3 414258 swap istruePASS2 //first pass completed now do second pass case0 114258 case1 212458 case2 312458 case3 412458 swap istrue PASS3 // third pass case0 112458 case1 212458 case2 312458 case3 412458 swap isfalse since swap is false we break from the loop and do not go for fourth and fifth pass
Program:-

package sorting;publicclassBubbleSort{//function to print arraypublicstaticvoidprint(int[] arr){for(int i=0;i<=arr.length-1;i++) Syst…