fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.List;
  3.  
  4.  
  5. // import java.util.concurrent.ConcurrentHashMap;
  6. // import java.util.concurrent.atomic.AtomicInteger;
  7. // import java.lang.reflect.Array;
  8. // import java.util.regex.MatchResult;
  9.  
  10.  
  11. // import javax.management.AttributeList;
  12.  
  13.  
  14. // import javax.xml.stream.events.Characters;
  15.  
  16.  
  17. class Main {
  18.  
  19.  
  20.    public int minCostOfRopes(int[] arr) {
  21.        MyMinHeap minHeap = new MyMinHeap();
  22.        if (arr.length <= 1) {
  23.            return 0;
  24.        }
  25.  
  26.  
  27.        // PriorityQueue<Integer> minHeap = new PriorityQueue<>();
  28.        for (int rope : arr) {
  29.            minHeap.insert(rope);
  30.        }
  31.  
  32.  
  33.        int minCostRopeSum = 0;
  34.  
  35.  
  36.        while (minHeap.myHeap.size() != 1) {
  37.            int firstRope = minHeap.fetchMin();
  38.            int secondRope = minHeap.fetchMin();
  39.  
  40.  
  41.            int newRopeLength = firstRope + secondRope;
  42.            minCostRopeSum += newRopeLength;
  43.  
  44.  
  45.            minHeap.insert(newRopeLength);
  46.        }
  47.        return minCostRopeSum;
  48.    }
  49.  
  50.  
  51.    public static void main(String[] args) {
  52.        Main solution = new Main();
  53.        int[] arr = new int[] { 4, 3, 2, 6 };
  54.        // MyMinHeap heap = new MyMinHeap();
  55.  
  56.  
  57.        System.out.println(solution.minCostOfRopes(arr));
  58.  
  59.  
  60.    }
  61. }
  62.  
  63.  
  64. class MyMinHeap {
  65.    List<Integer> myHeap;
  66.  
  67.  
  68.    public MyMinHeap() {
  69.        myHeap = new ArrayList<>();
  70.    }
  71.  
  72.  
  73.    public void insert(int val) {
  74.        myHeap.add(val);
  75.        sortArray(myHeap.size() - 1);
  76.    }
  77.  
  78.  
  79.    public void swap(int i, int j) {
  80.        int t = myHeap.get(i);
  81.        myHeap.set(i, myHeap.get(j));
  82.        myHeap.set(j, t);
  83.    }
  84.  
  85.  
  86.    public int fetchMin() {
  87.        if (myHeap.size() == 0)
  88.            return -1;
  89.        int minValue = myHeap.get(0);
  90.  
  91.  
  92.        int lastValue = myHeap.get(myHeap.size() - 1);
  93.        if (myHeap.size() != 0) {
  94.            myHeap.set(0, lastValue);
  95.              myHeap.remove(myHeap.size() - 1);  // <-- THIS LINE IS CRUCIAL
  96.  
  97.            sortArrayChild(0);
  98.        }
  99.        return minValue;
  100.    }
  101.    // . 0. 1. 2. 3
  102.    // [2, 3, 5, 6]
  103.  
  104.  
  105.    // parent = 1
  106.  
  107.  
  108.    public void sortArrayChild(int idx) {
  109.        int left = 2 * idx + 1;
  110.        int rightChild = 2 * idx + 2;
  111.  
  112.  
  113.        int currentNode = idx;
  114.        if (left < myHeap.size() && myHeap.get(left) < myHeap.get(currentNode)) {
  115.            System.out.println("Going in left" + currentNode);
  116.            currentNode = left;
  117.        }
  118.        if (rightChild < myHeap.size() && myHeap.get(rightChild) < myHeap.get(currentNode)) {
  119.            currentNode = rightChild;
  120.        }
  121.        if (currentNode != idx) {
  122.            System.out.println(currentNode);
  123.            swap(currentNode, idx);
  124.            sortArrayChild(currentNode);
  125.        }
  126.    }
  127.  
  128.  
  129.    public void sortArray(int idx) {
  130.        while (idx > 0) {
  131.            int node = (idx - 1) / 2;
  132.            if (myHeap.get(idx) < myHeap.get(node)) {
  133.                swap(idx, node);
  134.                idx = node;
  135.            } else {
  136.                break;
  137.            }
  138.        }
  139.    }
  140. }
  141.  
  142.  
  143. // [ 3, 5]
  144.  
  145.  
  146. // [ 3, 5, 2]
  147.  
  148.  
  149. // 2 < 3 -> [2, 5, 3]
  150.  
  151.  
  152. // 0 1 2 3
  153. // [2, 5, 3, 6]
  154.  
  155.  
  156. // parent =
  157.  
Success #stdin #stdout 0.15s 55468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Going in left0
2
Going in left0
1
29
https://ideone.com/kHndUm
language:
Java (HotSpot 12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!