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

Insertion Sort in JAVA

What is insertion sort?

It is a sorting technique that is based on the partitioning of array into two parts like selection sort, sorted and unsorted.

The process is:-

compare adjacent elements.
if(left > right)
Swap the element
{
check for sorted array whether it is still in sort manner(put j=i and loop in until j is not equal to zero)
- No
check for if(right<left)
swap
do it until at the end of position.
}

Implementation:-

Underline eleemnts are part of sorted arrayinside main array loop 142710333519424 (141027333519424 (here sorted array is distorted hence sorting has been done inside the loop) inside sorted array loop101427333519424 inside main array loop101427333519424 inside main array loop 101427333519424 inside main array loop101427333519424 inside sorted array loop 101427193335424 inside sorted array loop 101419273335424 inside main array loop 101419273335424 inside main array loop 101419273335424 inside sorted array loop101419273343542 inside…