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

Basics of System Design

This article is first one from the series of articles dedicated to system design interviews. Here i am going to present the base scenario to consider before starting to solve system design problems.
Questions to ask?
1) what is the number of requests a website will recieve in a day/month/second? 2) what is the amount of memory a website will deal in a day/month/second? 3) what is the number of servers that can accomodate these requests?
To answer this , first we need to remember the below numbers:-
1 million = 10 lakh = 1000000 = 10^6 1 billion = 1000 million = 10^9
1 KB = 1024 B = 10^31 MB= 10^6 = 1024 KB 1 GB= 10^9 = 1024 MB1 TB = 10^12 = 1024 GB
Memory we need to see in BytesRequests we need to see in numbers
example :-
suppose a website recieves 100M requests every month then:-
requests per day = request per month /24 = 416700 requests requests per second = requests per day / (24*3600) = 4.8 requests per second
memory:-
if we take 20:80 principal where 20 percent is write and 80 percent is …

Calculating size of User and Cache storage

user storage:-
it can be solved using same scenario as mentioned in first article .

https://tech.nazarmubeenworks.com/2019/08/basics-of-system-design-chapter-0.html


Suppose there are 12 Million of users are adding every year meaning 1 Million per month.
So if we consider 5 year there will be around 60 million of users. Now in terms of data we can look to our DB table and get information about it. A user will be generally having name , id , address , some forien keys .
Lets assume 10 columns with each column on an average storing 4 byte of data.
10*4 = 40 bytes of data for one user.
60 * 10^6 * 40 = 2400 * 10^6 = 2.4 * 10^9 = 2.4 GB of data we need to store only user values.
Also while calculating storage for the user there is also one important point we need to remember is of ids. If we are going to have 60 Million of users which means 60*10^6 users so unique id’s will be
as we know below figures are almost equal
2^10=10^3 then 60*(10^3)^2 = 2^20 *2^6
which means we almost need 26 …