Skip to content
Snippets Groups Projects

David

Open david.carballo requested to merge david.carballo/poo2019numeric:David into master
2 files
+ 83
4
Compare changes
  • Side-by-side
  • Inline

Files

@@ -8,14 +8,80 @@ import java.util.function.Function;
@@ -8,14 +8,80 @@ import java.util.function.Function;
final public class BinaryHeap
final public class BinaryHeap
{
{
final private List<Integer> lstBinaryHeap;
final private List<Integer> lstBinaryHeap;
private BinaryHeap()
private int taille;
 
public BinaryHeap()
{
{
lstBinaryHeap=new ArrayList<Integer>();
this.lstBinaryHeap=new ArrayList<Integer>();
 
this.taille=0;
}
}
public void push(int value)
public void push(int value)
{
{
 
this.taille++;
 
this.lstBinaryHeap.add(value);
 
this.sort();
 
}
 
 
private void sort()
 
{
 
int index=this.size()-1;
 
while(index!=0)
 
{
 
if(this.getParentNodeValue(index)<this.get(index))
 
{
 
//les place doivent etre changer
 
this.switchPlace(this.getParentNodeIndex(index),index);
 
//test la valeur d'a cote
 
}
 
else
 
{
 
//test si la branche existe
 
if(this.getSameLevelIndex(index)<this.size())
 
{
 
//si elle existe
 
index=this.getSameLevelIndex(index);//passe a l'index d'a coter
 
if(this.getParentNodeValue(index)<this.get(index))
 
{
 
//les place doivent etre changer
 
this.switchPlace(this.getParentNodeIndex(index),index);
 
}
 
}
 
}
 
index=this.getParentNodeIndex(index);
 
}
 
}
 
 
private void switchPlace(int index1,int index2)
 
{
 
int tmp;
 
tmp=this.lstBinaryHeap.get(index1);
 
this.set(index1,this.get(index2));
 
this.set(index2,tmp);
 
}
 
public void print()
 
{
 
for(int val:lstBinaryHeap)
 
{
 
System.out.println(val);
 
}
 
}
 
 
public int size()
 
{
 
return this.taille;
 
}
 
 
private int getSameLevelIndex(int index)
 
{
 
if(index%2==0)
 
{
 
return index-1;
 
}
 
else
 
{
 
return index+1;
 
}
}
}
private int getRightNodeIndex(int index)
private int getRightNodeIndex(int index)
Loading