Following is complete algorithm for finding the minimum cost for connecting n ropes.
Let there be n ropes of lengths stored in an array len[0..n-1]
1) Create a min heap and insert all lengths into the min heap.
2) Do following while number of elements in min heap is not one.
……a) Extract the minimum and second minimum from min heap
……b) Add the above two extracted values and insert the added value to the min-heap.
3) Return the value of only left item in min heap.
For 5,6,7,8 is 11+15+26=52 and not 55.
References:
http://www.geeksforgeeks.org/connect-n-ropes-minimum-cost/
Let there be n ropes of lengths stored in an array len[0..n-1]
1) Create a min heap and insert all lengths into the min heap.
2) Do following while number of elements in min heap is not one.
……a) Extract the minimum and second minimum from min heap
……b) Add the above two extracted values and insert the added value to the min-heap.
3) Return the value of only left item in min heap.
For 5,6,7,8 is 11+15+26=52 and not 55.
References:
http://www.geeksforgeeks.org/connect-n-ropes-minimum-cost/
static int minimumCost(int[] a) {
ReplyDeleteint len = a.length;
if (len == 0)
return -1;
if (len == 1)
return a[0];
int cost = 0;
minHeap(a);
while (len >= 2) {
int first = a[0];
a[0] = a[len - 1];
minHeapify(a, 0, len - 1);
a[0] = a[0] + first;
cost += a[0];
minHeapify(a, 0, len - 1);
len = len - 1;
}
return cost;
}
private static void minHeap(int[] a) {
int len = a.length;
for (int i = (len - 1) / 2; i > 0; i--) {
minHeapify(a, i, len);
}
}
private static void minHeapify(int[] a, int k, int n) {
if (k > n)
return;
int left = 2 * k + 1;
int right = 2 * k + 2;
int min = k;
if (left < n && a[left] < a[k]) {
min = left;
}
if (right < n && a[right] < a[min]) {
min = right;
}
if (k != min) {
swap(a, k, min);
minHeapify(a, min, k);
}
}
private static void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
Where is the main method?
ReplyDelete