Skip to content

Instantly share code, notes, and snippets.

@viniru
Created July 3, 2018 11:45
Show Gist options
  • Save viniru/0c1018ed9582417e3c7fd78801954153 to your computer and use it in GitHub Desktop.
Save viniru/0c1018ed9582417e3c7fd78801954153 to your computer and use it in GitHub Desktop.
Min Heap using java with build heap , delete by passing postion of the element to be deleted and insertion of an element.
import java.util.*;
import java.lang.Math;
public class MinHeap {
ArrayList<Integer> ar = new ArrayList<>();
int size = 0;
void delete(int pos)
{
ar.set(pos,ar.get(ar.size()-1));
ar.remove(ar.size()-1);
heapify(pos);
}
void insert(int val)
{
int i = ar.size();
ar.add(val);
int parent = i -1;
while(parent > 0)
{
parent = (int)Math.ceil((float)i/2 - 1);
if(ar.get(i) < ar.get(parent))
{
int temp = ar.get(parent);
ar.set(parent,ar.get(i));
ar.set(i,temp);
i = parent;
}
else break;
}
heapify(i);
}
void heapify(int i)
{
int size = ar.size()/2;
int parent=0;
int lchild=0;
int rchild = 0;
while(i < size)
{
lchild = 2*i+1;
rchild = 2*i+2;
parent = i;
if(rchild < ar.size() && ar.get(rchild) < ar.get(i))
i = rchild;
if(ar.get(lchild) < ar.get(i))
i = lchild;
if(i==parent)break;
int temp = ar.get(parent);
ar.set(parent,ar.get(i));
ar.set(i,temp);
}
}
void buildHeap()
{
int n = ar.size()/2;
while(n > 0)
{
heapify(--n);
}
}
void print()
{
for(int x : ar)
System.out.print(x+" ");
System.out.println();
}
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
MinHeap mh = new MinHeap();
while(sc.hasNextInt())
{
mh.ar.add(sc.nextInt());
}
mh.buildHeap();
mh.print();
mh.insert(-1);
mh.print();
mh.delete(1);
mh.print();
mh.insert(0);
mh.print();
}
}
@viniru
Copy link
Author

viniru commented Jul 3, 2018

please ask any doubts that you might have. I will reply

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment