import java.util.*;

public class GenericHeap <T extends Comparable <T> >{

ArrayList <T> data=new ArrayList<>();

HashMap<T,Integer> map=new HashMap<>();

public void add(T item) {

this.data.add(item);

map.put(item,this.data.size()-1);//

upHeapify(this.data.size()-1);

}

private void upHeapify(int ci) {

int pi=(ci-1)/2;

if(isLarger(this.data.get(ci),this.data.get(pi))>0) {

swap(pi,ci);

upHeapify(pi);

}

}

public void display() {

System.out.println(this.data);

}

public int size() {

return this.data.size();

}

public boolean isEmpty() {

return this.size()==0;

}

public T remove() {

this.swap(0,this.size()-1);

T rv=this.data.remove(this.size()-1);

downHeapify(0);

map.remove(rv);

return rv;

}

private void downHeapify(int pi) {

int lci=2*pi+1;

int rci=2*pi+2;

int mini=pi;

if(lci<this.size() && isLarger(this.data.get(lci),this.data.get(mini))>0) {

mini=lci;

}

if(rci<this.size() && isLarger(this.data.get(rci),this.data.get(mini))>0) {

mini=rci;

}

if(mini!=pi) {

this.swap(pi,mini);

downHeapify(mini);

}

}

public T get() {

return this.data.get(0);

}

//t has higher property then return +ve

private int isLarger(T t,T o) {

return t.compareTo(o);

}

private void swap(int i,int j) {

T ith=this.data.get(i);

T jth=this.data.get(j);

this.data.set(i,jth);

this.data.set(j,ith);

map.put(ith,j);

map.put(jth,i);

}

public void updatePriority(T item) {

int index=map.get(item);

//because we enter lesser value then old vale

upHeapify(index);

}

}