David

merge de david vers master

src/main/java/ch/hepia/structure/BinaryHeap.java

+package ch.hepia.structure;
+
+import java.util.List;
+import java.util.ArrayList;
+import java.util.function.DoubleFunction;
+import java.util.function.Function;
+import java.util.Random;
+
+final public class BinaryHeap
+{
+    final private List<Integer> lstBinaryHeap;
+    private int taille;
+    public BinaryHeap()
+    {
+      this.lstBinaryHeap=new ArrayList<Integer>();
+      this.taille=0;
+    }
+
+    public void push(int value)
+    {
+      this.taille++;
+      this.lstBinaryHeap.add(value);
+      this.sort();
+    }
+
+    public int peek()
+    {
+      return this.get(0);
+    }
+
+    public int pop()
+    {
+      int val=this.peek();
+      this.set(0,0);
+      this.sort();
+      if(this.size()>0)
+      {
+        this.lstBinaryHeap.remove(this.size()-1);
+        this.taille--;
+      }
+      return val;
+    }
+
+    public void addAll(List<Integer> lst)
+    {
+      for(int val:lst)
+      {
+        this.push(val);
+      }
+    }
+
+    public boolean isEmpty()
+    {
+      if(this.size()==0)
+      {
+        return true;
+      }
+      else
+      {
+        return false;
+      }
+    }
+
+    public int depth()
+    {
+      int index=this.size();
+      int dptCompteur=1;
+      while(index!=0)
+      {
+        index=this.getParentNodeIndex(index);
+        dptCompteur++;
+      }
+      return dptCompteur;
+    }
+
+    public boolean exist(int k)
+    {
+      for(int val:this.lstBinaryHeap)
+      {
+        if(k==val)
+        {
+          return true;
+        }
+      }
+      return false;
+    }
+
+    public static void populate(BinaryHeap heap, int size)
+    {
+      Random rand = new Random();
+      for(int i=0;i<size;i++)
+      {
+        heap.push(rand.nextInt(100));
+      }
+    }
+
+    private void sort()
+    {
+      int index=this.size()-1;
+      for(int i=0;i<this.depth();i++)
+      {
+        index=this.size()-1;
+       
+        while(index!=0)
+        {
+          //regarde si la valeur du parent est plus petit que l'enfant
+          if(this.getParentNodeValue(index)<this.get(index))
+          {
+            //les place doivent etre changer
+            this.switchPlace(this.getParentNodeIndex(index),index);
+      
+          }
+          else//test la valeur d'a cote
+          {
+            //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()
+    {
+      int index=0;
+      for(int etage=1;etage<=this.depth();etage++)//e
+      {
+        for(int nToShow=0;nToShow<Math.pow(2,etage-1);nToShow++)//n
+        {
+          if(index<this.size())
+          {
+            System.out.print(" "+this.get(index)+" ");
+          }
+          index++;
+        }
+        System.out.println("");
+      }
+      System.out.println("");
+    }
+
+    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)
+    {
+      return (2*index)+1;
+    }
+
+    private int getLeftNodeIndex(int index)
+    {
+      return (2*index)+2;
+    }
+
+    private int getParentNodeIndex(int index)
+    {
+      return (index-1) / 2;
+    }
+
+    private int getRightNodeValue(int index)
+    {
+      return this.get(this.getRightNodeIndex(index));
+    }
+
+    private int getLeftNodeValue(int index)
+    {
+      return this.get(this.getLeftNodeIndex(index));
+    }
+
+    private int getParentNodeValue(int index)
+    {
+      return this.get(this.getParentNodeIndex(index));
+    }
+
+    private int get(int index)
+    {
+      return this.lstBinaryHeap.get(index);
+    }
+    private void set(int index, int val)
+    {
+      this.lstBinaryHeap.set(index,val);
+    }
+}