Don't like ads? PRO users don't see any ads ;-)
Public Pastes

Nu'man Naufal - Binary Heap

By: numan on May 10th, 2012  |  syntax: Java 5  |  size: 21.13 KB  |  hits: 26  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. import java.io.BufferedWriter;
  2. import java.io.IOException;
  3. import java.io.OutputStreamWriter;
  4. import java.util.ArrayList;
  5.  
  6. /*
  7.  * To change this template, choose Tools | Templates
  8.  * and open the template in the editor.
  9.  */
  10.  
  11. /**
  12.  *
  13.  * @author
  14.  */
  15. public class MinBinaryHeapTree<T extends Comparable<T>> {
  16.  
  17.     /** array to contain data */
  18.     ArrayList<T> data;
  19.     /** size of the tree */
  20.     private int size;
  21.     /** writer */
  22.     private BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
  23.  
  24.     /**
  25.      * Default constructor
  26.      * @return -
  27.      */
  28.     public MinBinaryHeapTree() {
  29.         this.data = new ArrayList<T>();
  30.         this.size = 0;
  31.     }
  32.  
  33.     /**
  34.      * Constructor
  35.      * @param data - the data of the tree
  36.      * @return
  37.      */
  38.     public MinBinaryHeapTree(ArrayList<T> data) {
  39.         this();
  40.         this.size = data.size();
  41.         for (int ii = 0; ii < data.size(); ii++) {
  42.             this.data.add(data.get(ii));
  43.         }
  44.         heapify();
  45.     }
  46.    
  47.     public void heapSort() {
  48.         int size = data.size();
  49.         ArrayList sortedList = new ArrayList<T>();
  50.         while (data.size() > 0) {
  51.             sortedList.add(deleteMin());
  52.         }
  53.         data = sortedList;
  54.     }
  55.     /**
  56.      * Insert data into array
  57.      * @param value - the node
  58.      * @return -
  59.      */
  60.     public void insert(T value) {
  61.         // LENGKAPI
  62.         data.add(value);
  63.         percolateUp(data.size() - 1);
  64.         size++;
  65.     }
  66.  
  67.     /**
  68.      * Delete the maximum data of the array
  69.      * @return -
  70.      */
  71.     public T deleteMin() {
  72.         // LENGKAPI
  73.         T min = data.get(0);
  74.         data.set(0, data.get(data.size()-1));
  75.         data.remove(data.size()-1);
  76.         if(data.size() > 1) {
  77.             percolateDown(0);
  78.         }        
  79.         size--;
  80.         return min;
  81.     }
  82.  
  83.     /**
  84.      * Check the array is empty or not
  85.      * @return boolean
  86.      */
  87.     public boolean isEmpty() {
  88.         return size == 0;
  89.     }
  90.  
  91.     /**
  92.      * Method to print the array
  93.      * @return -
  94.      */
  95.     public void print() throws IOException {
  96.         for (int ii = 0; ii < size - 1; ii++) {
  97.             writer.write(data.get(ii).toString() + ",");
  98.         }
  99.         if (size != 0) {
  100.             writer.write(data.get(size - 1).toString());
  101.         }
  102.         writer.write("\n");
  103.     }
  104.  
  105.     /**
  106.      * Flush the writer
  107.      * @return
  108.      */
  109.     public void flushWriter() throws IOException {
  110.         writer.flush();
  111.     }
  112.  
  113.     /**
  114.      * Make the tree into heap data structure
  115.      * @return -
  116.      */
  117.     private void heapify() {
  118.         // LENGKAPI
  119.         for(int parent = parentOf(data.size()-1); parent >= 0; parent--) {
  120.             //percolatedown dari semua parent di tree
  121.             percolateDown(parent);
  122.         }
  123.     }
  124.  
  125.     /**
  126.      * Method to set element in the array
  127.      * @param value - the new element
  128.      * @param leaf - index of the element
  129.      * @return -
  130.      */
  131.     private void setElementAt(T value, int leaf) {
  132.         data.set(leaf, value);
  133.     }
  134.  
  135.     /**
  136.      * Method to obtain the parent index of a node
  137.      * @param index - the node index
  138.      * @return index of the parent
  139.      */
  140.     private int parentOf(int index) {
  141.         // LENGKAPI
  142.         return (index - 1) / 2;
  143.     }
  144.  
  145.     /**
  146.      * Method to obtain the left child index of a node
  147.      * @param index - the node index
  148.      * @return index of the left child
  149.      */
  150.     private int leftChildOf(int index) {
  151.         // LENGKAPI
  152.         return 2 * index + 1;
  153.     }
  154.  
  155.     /**
  156.      * Method to obtain the right child index of a node
  157.      * @param index - the node index
  158.      * @return index of the right child
  159.      */
  160.     private int rightChildOf(int index) {
  161.         // LENGKAPI
  162.         return 2 * index + 2;
  163.     }
  164.  
  165.     /**
  166.      * Percolate Up
  167.      * @param leaf - the index of the element
  168.      * @return -
  169.      */
  170.     private void percolateUp(int leaf) {
  171.         // LENGKAPI
  172.         int parent = parentOf(leaf); //ambil index parent
  173.         Comparable value = (Comparable) data.get(leaf); //ambil nilai dari leaf
  174.         while (leaf > 0 && (value.compareTo((Comparable) data.get(parent)) < 0)) { //jika nilai leaf lebih kecil daripada nilai parent
  175.             data.set(leaf, (T) data.get(parent)); //menurunkan parent
  176.             leaf = parent; //menaikkan index leaf
  177.             parent = parentOf(leaf); //menaikkan index parent
  178.         }
  179.         data.set(leaf, (T) value); //menempatkan nilai leaf ke tempat seharusnya
  180.     }
  181.  
  182.     /**
  183.      * Percolate Down
  184.      * @param root - the index of root
  185.      * @return
  186.      */
  187.     private void percolateDown(int root) {
  188.         // LENGKAPI
  189.         int heapSize = data.size(); //size dari array
  190.         Comparable value = (Comparable) data.get(root); //nilai dari node paling atas
  191.         while (root < heapSize) { //selama index node tidak melebihi size
  192.             int childpos = leftChildOf(root); //menyimpan child sebelah kiri
  193.             if (childpos < heapSize) { //jika index child sebelah kiri kurang dari size
  194.                 //bila child sebelah kanan ada dan child sebelah kanan lebih kecil nilainya dari child sebelah kiri
  195.                 if (rightChildOf(root) < heapSize && ((Comparable) data.get(childpos + 1)).compareTo(((Comparable) data.get(childpos))) < 0) {
  196.                     childpos++; //child yang dituju menjadi child sebelah kanan
  197.                 }
  198.                 //bila nilai child lebih besar dari nilai root
  199.                 if (((Comparable)data.get(childpos)).compareTo((Comparable) value) < 0) {
  200.                     data.set(root, data.get(childpos)); //menaikkan child
  201.                     root = childpos; //menurunkan index
  202.                 } else {
  203.                     data.set(root, (T) value); //menempatkan nilai parent ke tempat seharusnya
  204.                     return;
  205.                 }
  206.             } else { //bila child lebih kecil
  207.                 data.set(root, (T) value); //langsung ditempatkan
  208.                 return;
  209.             }
  210.         }
  211.     }
  212. }
  213.  
  214.  
  215. import java.io.BufferedWriter;
  216. import java.io.IOException;
  217. import java.io.OutputStreamWriter;
  218. import java.util.ArrayList;
  219.  
  220. /*
  221.  * To change this template, choose Tools | Templates
  222.  * and open the template in the editor.
  223.  */
  224.  =================================================================================================
  225. /**
  226.  *
  227.  * @author
  228.  */
  229. public class MaxBinaryHeapTree<T extends Comparable<T>> {
  230.  
  231.     /** array to contain data */
  232.     private ArrayList<T> data;
  233.     /** size of the tree */
  234.     private int size;
  235.     /** writer */
  236.     private BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
  237.  
  238.     /**
  239.      * Default constructor
  240.      * @return -
  241.      */
  242.     public MaxBinaryHeapTree() {
  243.         this.data = new ArrayList<T>();
  244.         this.size = 0;
  245.     }
  246.  
  247.     /**
  248.      * Constructor
  249.      * @param data - the data of the tree
  250.      * @return
  251.      */
  252.     public MaxBinaryHeapTree(ArrayList<T> data) {
  253.         this();
  254.         this.size = data.size();
  255.         for (int ii = 0; ii < data.size(); ii++) {
  256.             this.data.add(data.get(ii));
  257.         }
  258.         heapify();
  259.     }
  260.  
  261.     /**
  262.      * Insert data into array
  263.      * @param value - the node
  264.      * @return -
  265.      */
  266.     public void insert(T value) {
  267.         // LENGKAPI
  268.         data.add(value);
  269.         percolateUp(data.size() - 1);
  270.         size++;
  271.     }
  272.  
  273.     /**
  274.      * Delete the maximum data of the array
  275.      * @return -
  276.      */
  277.     public T deleteMax() {
  278.         // LENGKAPI
  279.         T max = data.get(0);
  280.         data.set(0, data.get(data.size()-1));
  281.         data.remove(data.size()-1);
  282.         if(data.size() > 1) {
  283.             percolateDown(0);
  284.         }        
  285.         size--;
  286.         return max;
  287.     }
  288.  
  289.     /**
  290.      * Check the array is empty or not
  291.      * @return boolean
  292.      */
  293.     public boolean isEmpty() {
  294.         return size == 0;
  295.     }
  296.  
  297.     /**
  298.      * Method to print the array
  299.      * @return -
  300.      */
  301.     public void print() throws IOException {
  302.         for (int ii = 0; ii < size - 1; ii++) {
  303.             writer.write(data.get(ii).toString() + ",");
  304.         }
  305.         if (size != 0) {
  306.             writer.write(data.get(size - 1).toString());
  307.         }
  308.         writer.write("\n");
  309.     }
  310.  
  311.     /**
  312.      * Flush the writer
  313.      * @return
  314.      */
  315.     public void flushWriter() throws IOException {
  316.         writer.flush();
  317.     }
  318.  
  319.     /**
  320.      * Make the tree into heap data structure
  321.      * @return -
  322.      */
  323.     private void heapify() {
  324.         // LENGKAPI
  325.         for(int parent = parentOf(data.size()-1); parent >= 0; parent--) {
  326.             //percolatedown dari semua parent di tree
  327.             percolateDown(parent);
  328.         }
  329.     }
  330.  
  331.     /**
  332.      * Method to set element in the array
  333.      * @param value - the new element
  334.      * @param leaf - index of the element
  335.      * @return -
  336.      */
  337.     private void setElementAt(T value, int leaf) {
  338.         data.set(leaf, value);
  339.     }
  340.  
  341.     /**
  342.      * Method to obtain the parent index of a node
  343.      * @param index - the node index
  344.      * @return index of the parent
  345.      */
  346.     private int parentOf(int index) {
  347.         // LENGKAPI
  348.         return (index - 1) / 2;
  349.     }
  350.  
  351.     /**
  352.      * Method to obtain the left child index of a node
  353.      * @param index - the node index
  354.      * @return index of the left child
  355.      */
  356.     private int leftChildOf(int index) {
  357.         // LENGKAPI
  358.         return 2 * index + 1;
  359.     }
  360.  
  361.     /**
  362.      * Method to obtain the right child index of a node
  363.      * @param index - the node index
  364.      * @return index of the right child
  365.      */
  366.     private int rightChildOf(int index) {
  367.         // LENGKAPI
  368.         return 2 * index + 2;
  369.     }
  370.  
  371.     /**
  372.      * Percolate Up
  373.      * @param leaf - the index of the element
  374.      * @return -
  375.      */
  376.     private void percolateUp(int leaf) {
  377.         // LENGKAPI
  378.         int parent = parentOf(leaf); //ambil index parent
  379.         Comparable value = (Comparable) data.get(leaf); //ambil nilai dari leaf
  380.         while (leaf > 0 && (value.compareTo((Comparable) data.get(parent)) < 0)) { //jika nilai leaf lebih besar daripada nilai parent
  381.             data.set(leaf, (T) data.get(parent)); //menurunkan parent
  382.             leaf = parent; //menaikkan index leaf
  383.             parent = parentOf(leaf); //menaikkan index parent
  384.         }
  385.         data.set(leaf, (T) value); //menempatkan nilai leaf ke tempat seharusnya
  386.     }
  387.  
  388.     /**
  389.      * Percolate Down
  390.      * @param root - the index of root
  391.      * @return
  392.      */
  393.     private void percolateDown(int root) {
  394.         // LENGKAPI
  395.         int heapSize = data.size(); //size dari array
  396.         Comparable value = (Comparable) data.get(root); //nilai dari node paling atas
  397.         while (root < heapSize) { //selama index node tidak melebihi size
  398.             int childpos = leftChildOf(root); //menyimpan child sebelah kiri
  399.             if (childpos < heapSize) { //jika index child sebelah kiri kurang dari size
  400.                 //bila child sebelah kanan ada dan child sebelah kanan lebih besar nilainya dari child sebelah kiri
  401.                 if (rightChildOf(root) < heapSize && ((Comparable) data.get(childpos + 1)).compareTo(((Comparable) data.get(childpos))) < 0) {
  402.                     childpos++; //child yang dituju menjadi child sebelah kanan
  403.                 }
  404.                 //bila nilai child lebih besar dari nilai root
  405.                 if (((Comparable)data.get(childpos)).compareTo((Comparable) value) < 0) {
  406.                     data.set(root, data.get(childpos)); //menaikkan child
  407.                     root = childpos; //menurunkan index
  408.                 } else {
  409.                     data.set(root, (T) value); //menempatkan nilai parent ke tempat seharusnya
  410.                     return;
  411.                 }
  412.             } else { //bila child lebih kecil
  413.                 data.set(root, (T) value); //langsung ditempatkan
  414.                 return;
  415.             }
  416.         }
  417.     }
  418. }
  419.  
  420. ================================================================================================
  421. Quiz Rabu
  422.  
  423. import java.util.StringTokenizer;
  424. import java.util.ArrayList;
  425. import java.io.BufferedReader;
  426. import java.io.InputStreamReader;
  427. import java.io.BufferedWriter;
  428. import java.io.OutputStreamWriter;
  429. import java.io.IOException;
  430.  
  431. /**
  432.  * SDA1112K2A Class
  433.  * Contain the main method to execute the program
  434.  * @author Satyadharma Tirtarasa & Pandu Wicaksono
  435.  */
  436. public class SDA1112K2A {
  437.  
  438.     /**
  439.      * Main method of this program
  440.      * @param args - first argument of the program (not used in actual
  441.      * implementation)
  442.      * @return -
  443.      */
  444.     public static void main(String[] args) throws IOException {
  445.         // LENGKAPI
  446.         BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  447.         StringTokenizer tokIn = new StringTokenizer(in.readLine(), ",");
  448.         int masukan = Integer.parseInt(tokIn.nextToken());
  449.         int banyakOperasi = Integer.parseInt(tokIn.nextToken());
  450.         MaxBinaryHeapTree mbTree = new MaxBinaryHeapTree();
  451.         for (int i = 0; i < masukan; i++) {
  452.             StringTokenizer tok = new StringTokenizer(in.readLine(), ",");
  453.             mbTree.insert(new Club(tok.nextToken(), Integer.parseInt(tok.nextToken()), Integer.parseInt(tok.nextToken()),Integer.parseInt(tok.nextToken()),Integer.parseInt(tok.nextToken()),Integer.parseInt(tok.nextToken())));            
  454.         }
  455.         mbTree.print();
  456.         for(int i = 0; i < banyakOperasi; i++) {
  457.            StringTokenizer tok = new StringTokenizer(in.readLine());
  458.            if(tok.nextToken().equals("DanaTidakMencukupi")) {
  459.                mbTree.deleteMax();
  460.                mbTree.print();
  461.            } else {
  462.                String club = tok.nextToken();
  463.                StringTokenizer tokClub = new StringTokenizer(club, ",");
  464.                mbTree.insert(new Club(tokClub.nextToken(), Integer.parseInt(tokClub.nextToken()), Integer.parseInt(tokClub.nextToken()),Integer.parseInt(tokClub.nextToken()),Integer.parseInt(tokClub.nextToken()),Integer.parseInt(tokClub.nextToken())));
  465.                mbTree.print();
  466.            }
  467.         }
  468.         mbTree.flushWriter();
  469.     }
  470. }
  471.  
  472. /**
  473.  * MaxBinaryHeapTree Class
  474.  * Represent a MaxBinaryHeapTree to solve the problem
  475.  * @author Satyadharma Tirtarasa & Pandu Wicaksono
  476.  */
  477. class MaxBinaryHeapTree<T extends Comparable<T>> {
  478.  
  479.     /** array to contain data */
  480.     private ArrayList<T> data;
  481.     /** size of the tree */
  482.     private int size;
  483.     /** writer */
  484.     private BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
  485.  
  486.     /**
  487.      * Default constructor
  488.      * @return -
  489.      */
  490.     public MaxBinaryHeapTree() {
  491.         this.data = new ArrayList<T>();
  492.         this.size = 0;
  493.     }
  494.  
  495.     /**
  496.      * Constructor
  497.      * @param data - the data of the tree
  498.      * @return
  499.      */
  500.     public MaxBinaryHeapTree(ArrayList<T> data) {
  501.         this();
  502.         this.size = data.size();
  503.         for (int ii = 0; ii < data.size(); ii++) {
  504.             this.data.add(data.get(ii));
  505.         }
  506.         heapify();
  507.     }
  508.  
  509.     /**
  510.      * Insert data into array
  511.      * @param value - the node
  512.      * @return -
  513.      */
  514.     public void insert(T value) {
  515.         // LENGKAPI
  516.         data.add(value);
  517.         percolateUp(data.size() - 1);
  518.         size++;
  519.     }
  520.  
  521.     /**
  522.      * Delete the maximum data of the array
  523.      * @return -
  524.      */
  525.     public T deleteMax() {
  526.         // LENGKAPI
  527.         T max = data.get(0);
  528.         data.set(0, data.get(data.size()-1));
  529.         data.remove(data.size()-1);
  530.         if(data.size() > 1) {
  531.             percolateDown(0);
  532.         }        
  533.         size--;
  534.         return max;
  535.     }
  536.  
  537.     /**
  538.      * Check the array is empty or not
  539.      * @return boolean
  540.      */
  541.     public boolean isEmpty() {
  542.         return size == 0;
  543.     }
  544.  
  545.     /**
  546.      * Method to print the array
  547.      * @return -
  548.      */
  549.     public void print() throws IOException {
  550.         for (int ii = 0; ii < size - 1; ii++) {
  551.             writer.write(data.get(ii).toString() + ",");
  552.         }
  553.         if (size != 0) {
  554.             writer.write(data.get(size - 1).toString());
  555.         }
  556.         writer.write("\n");
  557.     }
  558.  
  559.     /**
  560.      * Flush the writer
  561.      * @return
  562.      */
  563.     public void flushWriter() throws IOException {
  564.         writer.flush();
  565.     }
  566.  
  567.     /**
  568.      * Make the tree into heap data structure
  569.      * @return -
  570.      */
  571.     private void heapify() {
  572.         // LENGKAPI
  573.         for(int parent = parentOf(data.size()-1); parent >= 0; parent--) {
  574.             percolateDown(parent);
  575.         }
  576.     }
  577.  
  578.     /**
  579.      * Method to set element in the array
  580.      * @param value - the new element
  581.      * @param leaf - index of the element
  582.      * @return -
  583.      */
  584.     private void setElementAt(T value, int leaf) {
  585.         data.set(leaf, value);
  586.     }
  587.  
  588.     /**
  589.      * Method to obtain the parent index of a node
  590.      * @param index - the node index
  591.      * @return index of the parent
  592.      */
  593.     private int parentOf(int index) {
  594.         // LENGKAPI
  595.         return (index - 1) / 2;
  596.     }
  597.  
  598.     /**
  599.      * Method to obtain the left child index of a node
  600.      * @param index - the node index
  601.      * @return index of the left child
  602.      */
  603.     private int leftChildOf(int index) {
  604.         // LENGKAPI
  605.         return 2 * index + 1;
  606.     }
  607.  
  608.     /**
  609.      * Method to obtain the right child index of a node
  610.      * @param index - the node index
  611.      * @return index of the right child
  612.      */
  613.     private int rightChildOf(int index) {
  614.         // LENGKAPI
  615.         return 2 * index + 2;
  616.     }
  617.  
  618.     /**
  619.      * Percolate Up
  620.      * @param leaf - the index of the element
  621.      * @return -
  622.      */
  623.     private void percolateUp(int leaf) {
  624.         // LENGKAPI
  625.         int parent = parentOf(leaf);
  626.         Comparable value = (Comparable) data.get(leaf);
  627.         while (leaf > 0 && (value.compareTo((Comparable) data.get(parent)) < 0)) {
  628.             data.set(leaf, (T) data.get(parent));
  629.             leaf = parent;
  630.             parent = parentOf(leaf);
  631.         }
  632.         data.set(leaf, (T) value);
  633.     }
  634.  
  635.     /**
  636.      * Percolate Down
  637.      * @param root - the index of root
  638.      * @return
  639.      */
  640.     private void percolateDown(int root) {
  641.         // LENGKAPI
  642.         int heapSize = data.size();
  643.         Comparable value = (Comparable) data.get(root);
  644.         while (root < heapSize) {
  645.             int childpos = leftChildOf(root);
  646.             if (childpos < heapSize) {
  647.                 if (rightChildOf(root) < heapSize && ((Comparable) data.get(childpos + 1)).compareTo(((Comparable) data.get(childpos))) < 0) {
  648.                     childpos++;
  649.                 }
  650.                 if (((Comparable)data.get(childpos)).compareTo((Comparable) value) < 0) {
  651.                     data.set(root, data.get(childpos));
  652.                     root = childpos;
  653.                 } else {
  654.                     data.set(root, (T) value);
  655.                     return;
  656.                 }
  657.             } else {
  658.                 data.set(root, (T) value);
  659.                 return;
  660.             }
  661.         }
  662.     }
  663. }
  664.  
  665. /**
  666.  * Club Class
  667.  * Represent a football club used to solve the problem
  668.  * @author Satyadharma Tirtarasa & Pandu Wicaksono
  669.  */
  670. class Club implements Comparable<Club> {
  671.  
  672.     /** The name of the club */
  673.     private String name;
  674.     /** The number of wins */
  675.     private int win;
  676.     /** The number of draw */
  677.     private int draw;
  678.     /** The number of lose */
  679.     private int lose;
  680.     /** The number of goal scored */
  681.     private int goalScored;
  682.     /** The number of goal allowed */
  683.     private int goalAllowed;
  684.     int point;
  685.     int selisihGol;
  686.  
  687.     /**
  688.      * Constructor
  689.      * @param name
  690.      * @param win
  691.      * @param draw
  692.      * @param lose
  693.      * @param goalScored
  694.      * @param goalAllowed
  695.      * @return -
  696.      */
  697.     public Club(String name, int win, int draw, int lose, int goalScored, int goalAllowed) {
  698.         this.name = name;
  699.         this.win = win;
  700.         this.draw = draw;
  701.         this.lose = lose;
  702.         this.goalScored = goalScored;
  703.         this.goalAllowed = goalAllowed;
  704.         point = 3 * win + draw;
  705.         selisihGol = goalScored - goalAllowed;
  706.     }
  707.  
  708.     /**
  709.      * CompareTo method
  710.      * @param other - the other club to compare with this club
  711.      * @return the result of the comparison
  712.      */
  713.     public int compareTo(Club other) {
  714.         // LENGKAPI
  715.         if (this.point > other.point) {
  716.             return -1;
  717.         } else if (this.point < other.point) {
  718.             return 1;
  719.         } else {
  720.             if (this.selisihGol > other.selisihGol) {
  721.                 return -1;
  722.             } else if (this.selisihGol < other.selisihGol) {
  723.                 return 1;
  724.             } else {
  725.                 if (this.goalScored > other.goalScored) {
  726.                     return -1;
  727.                 } else if (this.goalScored < other.goalScored) {
  728.                     return 1;
  729.                 } else {
  730.                     return this.name.compareTo(other.name);
  731.                 }
  732.             }
  733.         }
  734.     }
  735.  
  736.     /**
  737.      * toString method
  738.      * @return -
  739.      */
  740.     public String toString() {
  741.         return name;
  742.     }
  743. }
create a new version of this paste RAW Paste Data