Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Nov 15th, 2018 90 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. import java.util.*;
  2.  
  3. //import resources.*;
  4.  
  5. // NEUSTE : 15.11.18 , 20:37
  6. public class Delivery {
  7.  
  8.  
  9.     class MaxHeap extends Heap {
  10.         MaxHeap(int[] elements) {
  11.             super(elements);
  12.         }
  13.  
  14.         @Override
  15.         public int remove(){
  16.             //TODO implement here. Removes the top element, restores heap and returns the removed element.
  17.            swap(0 , end);
  18.            int tmp = this.elements[end];
  19.             --end;
  20.             heap();
  21.  
  22.             return tmp;
  23.         }
  24.  
  25.         @Override
  26.         public void add(int ele){
  27.             //TODO implement here
  28.             if (end == this.elements.length-1){
  29.                 int [] tmp = new int[elements.length+1];
  30.                 for(int i = 0 ; i< elements.length;i++)
  31.                 {
  32.                     tmp[i] = elements[i];
  33.  
  34.                 }
  35.                 tmp[tmp.length-1] = ele;
  36.                 elements = tmp;
  37.                 end++;
  38.  
  39.             } else if(end < this.elements.length-1){
  40.  
  41.                 this.elements[end++] = ele;
  42.             }
  43.             heap();
  44.         }
  45.  
  46.  
  47.  
  48.         @Override
  49.         protected void heap(){
  50.             //TODO implement here and LEAVE the saveStep() at the end!!
  51.             int startIndex = ((end) / 2); //Start Indes, erstes Parent mit Child
  52.  
  53.             //Schleife durchlauft von rechts nach links das array unt ruft uebrladene meth auf mit pos des curentParent
  54.             for(int i = startIndex; i >= 0; --i) {
  55.                 heap(i);
  56.             }
  57.  
  58.             saveStep();
  59.  
  60.         }
  61.         public boolean doIExist(int pos)
  62.         {
  63.             return pos<=end;
  64.         }
  65.         boolean compareElements(int l , int r)
  66.         {
  67.             return elements[l] > elements[r];
  68.         }
  69.  
  70.         protected void heap(int curParent){
  71.  
  72.             int curLeftChild = (2 * curParent) + 1;
  73.             int curRightChild = (2 * curParent) + 2;
  74.             int largestChild = curParent;
  75.  
  76.             if( doIExist(curLeftChild)&& compareElements(curLeftChild,curParent) )
  77.             {
  78.                 largestChild = curLeftChild;
  79.             }
  80.  
  81.             if( doIExist(curRightChild) && compareElements(curRightChild,curLeftChild) )
  82.             {
  83.                 if(compareElements(curRightChild,curParent))
  84.                 {
  85.                     largestChild = curRightChild;
  86.                 }
  87.  
  88.             }
  89.             if( largestChild != curParent )
  90.             {
  91.                 swap(curParent,largestChild);
  92.                 heap(largestChild);
  93.             }
  94.  
  95.         }
  96.         //Swap fuer zwei Elemente in einem Array
  97.         public void swap(int x, int y){
  98.             int tmp = this.elements[x];
  99.             this.elements[x] = this.elements[y];
  100.             this.elements[y] = tmp;
  101.  
  102.         }
  103.  
  104.         @Override
  105.         public int[] sort(){
  106.             //TODO implement here. Sort heap in-place using the given methods and return the sorted sequence.
  107.  
  108.                 while ( end >1){
  109.                     remove();
  110.                    // heap();
  111.                 }
  112.                 if(end == 1)
  113.                 {
  114.                     swap(0,1);
  115.                 }
  116.  
  117.  
  118.             return this.elements;
  119.         }
  120.  
  121.     }
  122.  
  123.     public Heap getMaxHeap(int[] sequence){
  124.         return new MaxHeap(sequence);
  125.     }
  126.  
  127.     class MinHeap extends Heap {
  128.         MinHeap(int[] elements) {
  129.             super(elements);
  130.         }
  131.  
  132.         @Override
  133.         public int remove(){
  134.             //TODO implement here. Removes the top element, restores heap and returns the removed element.
  135.             swap(0 , end);
  136.            // System.out.println("pre : "+end);
  137.             int tmp = this.elements[end];
  138.             --end;
  139.            // System.out.println("post : "+end);
  140.             heap();
  141.  
  142.  
  143.             return tmp;
  144.         }
  145.  
  146.         @Override
  147.         public void add(int ele){
  148.             //TODO implement here
  149.             if (end == this.elements.length-1){
  150.                 int [] tmp = new int[elements.length+1];
  151.                 for(int i = 0 ; i< elements.length;i++)
  152.                 {
  153.                     tmp[i] = elements[i];
  154.  
  155.                 }
  156.                 tmp[tmp.length-1] = ele;
  157.                 elements = tmp;
  158.                 end++;
  159.  
  160.             } else if(end < this.elements.length-1){
  161.  
  162.                 this.elements[end++] = ele;
  163.             }
  164.             heap();
  165.         }
  166.  
  167.         @Override
  168.         protected void heap(){
  169.             //TODO implement here and LEAVE the saveStep() at the end!!
  170.             int startIndex = ((this.elements.length - 1) / 2);
  171.  
  172.  
  173.             for(int i = startIndex; i >= 0; --i) {
  174.                 heap(i);
  175.             }
  176.             saveStep();
  177.         }
  178.         public boolean doIExist(int pos)
  179.         {
  180.             return pos<=end;
  181.         }
  182.         boolean compareElements(int l , int r)
  183.         {
  184.             return elements[l] > elements[r];
  185.         }
  186.  
  187.         protected void heap(int curParent){
  188.  
  189.             int curLeftChild = (2 * curParent) + 1;
  190.             int curRightChild = (2 * curParent) + 2;
  191.             int largestChild = curParent;
  192.  
  193.             if( doIExist(curLeftChild)&& compareElements(curParent,curLeftChild) )
  194.             {
  195.                 largestChild = curLeftChild;
  196.             }
  197.  
  198.             if( doIExist(curRightChild) && compareElements(curLeftChild,curRightChild) )
  199.             {
  200.                 if(compareElements(curParent,curRightChild))
  201.                 {
  202.                     largestChild = curRightChild;
  203.                 }
  204.  
  205.             }
  206.             if( largestChild != curParent )
  207.             {
  208.                 swap(curParent,largestChild);
  209.                 heap(largestChild);
  210.             }
  211.  
  212.         }
  213.         //Swap fuer zwei Elemente in einem Array
  214.         public void swap(int x, int y){
  215.             int tmp = this.elements[x];
  216.             this.elements[x] = this.elements[y];
  217.             this.elements[y] = tmp;
  218.  
  219.         }
  220.  
  221.         @Override
  222.         public int[] sort(){
  223.             //TODO implement here. Sort heap in-place using the given methods and return the sorted sequence.
  224.             int s = end;
  225.             while ( end >1){
  226.                 remove();
  227.                 //heap();
  228.             }
  229.             if(end == 1)
  230.             {
  231.                 swap(0,1);
  232.             }
  233.             for(int i = 1 ; i<=(elements.length)/2 ; i++)
  234.             {
  235.                 swap(i-1,elements.length-i);
  236.             }
  237.  
  238.             return this.elements;
  239.         }
  240.  
  241.     }
  242.  
  243.     public Heap getMinHeap(int[] sequence){
  244.         return new MinHeap(sequence);
  245.     }
  246.  
  247.  
  248.  
  249. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top