贪心算法 - 最小生成树 Kruskal算法
关于最小生成树的概念，请参考前一篇文章：Prim算法。
Kruskal算法：
不停地循环，每一次都寻找两个顶点，这两个顶点不在同一个真子集里，且边上的权值最小。
把找到的这两个顶点联合起来。
初始时，每个顶点各自属于自己的子集合，共n个子集合。
每一步操作，都会将两个子集合融合成一个，进而减少一个子集合。
结束时，所有的顶点都在同一个子集合里，这个子集合就是最小生成树。
例子：
算法过程为：
代码实现：
/** * 0 * / \ * 1 2 * / \ * 3 4 * @author xuefeng * */public class MinHeap<T extends Comparable> {private Object[] data;private int size;public MinHeap(int capacity) {data = new Object[capacity];size = 0;}public boolean add(T val) {if (size >= data.length)return false;int i = size, p;data[size] = val;size++;while (i > 0) {p = parentIndex(i);if (get(i).compareTo(get(p)) < 0) {swap(data, i, p);} else {break;}i = p;}return true;}public T remove(int index) {if (index >= size)return null;int i = index, left, right, p;T val = (T) data[index];data[index] = data[size - 1];size--;while (!isLeaf(i)) {left = leftIndex(i);right = rightIndex(i);p = i;i = right >= size || get(left).compareTo(get(right)) < 0 ? left: right;if (get(i).compareTo(get(p)) < 0) {swap(data, i, p);}}return val;}public T removeMin() {return remove(0);}public T get(int index) {if (index >= size)throw new IllegalArgumentException("index is greater than size : "+ index);return (T) data[index];}private static int leftIndex(int index) {return 2 * index + 1;}private static int rightIndex(int index) {return 2 * index + 2;}private static int parentIndex(int i) {return i % 2 == 0 ? i / 2 - 1 : i / 2;}private boolean isLeaf(int index) {return leftIndex(index) >= size;}private void swap(Object[] data, int i1, int i2) {Object temp = data[i1];data[i1] = data[i2];data[i2] = temp;}}