摘要：最小堆，Java实现最小堆

前面我们实现了最大堆，但是有时候我们却需要最下堆，比如需要最小优先队列的时候，最小堆来实现复杂度将会变成O(lgN)，所以这里用Java实现一个最小堆的工具类：

/**
  *    最小堆
 * @author suibibk@qq.com
 *
 */
public class MinHead<E extends Comparable<E>> {
    //这里使用数组来实现
    private ArrayList<E> data;
    public MinHead(int capacity) {
        data = new ArrayList<>(capacity);
    }
    public MinHead() {
        data  = new ArrayList<>();
    }
    //返回堆中元素的个数
    public int getSize() {
        return data.size();
    }
    //返回二叉树中索引为index的节点的父节点索引
    public int parent(int index) {
        if(index == 0) {
            throw new IllegalArgumentException("index-0 dosen't have parent");
        }
        return (index-1)/2;
    }
    //返回完全二叉树中索引为index的节点的左孩子的索引
    private int leftChild(int index) {
        return index*2+1;
    }
    //返回完全二叉树中索引为index的节点的右孩子的索引
    private int rightChild(int index) {
        return index * 2 + 2;
    }
    //交换索引为i、j的值
    private void swap(int i, int j) {
        E t = data.get(i);
        data.set(i, data.get(j));
        data.set(j, t);
    }
    //向堆中添加元素
    public void add(E e) {
        data.add(e);
        siftUp(data.size() - 1);
    }
    private void siftUp(int k) {
        //k不能是根节点，并且k的值要比父节点的值小
        while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) > 0) {
            swap(k, parent(k));
            k = parent(k);
        }
    }
  //看堆中最小的元素
    public E findMin() {
        if (data.size() == 0)
            throw new IllegalArgumentException("Can not findMax when heap is empty");
        return data.get(0);
    }
    /**
     * 当修改了堆中一些元素后，这里需要重新建堆
     */
    public void rebuildHead(int index) {
       siftDown(index);
        siftUp(index);
    }
    //取出堆中最小的元素
    public E extractMin() {
        E ret = findMin();
        swap(0, data.size() - 1);
        data.remove(data.size() - 1);
        siftDown(0);
        return ret;
    }
    private void siftDown(int k) {
        //leftChild存在
        while (leftChild(k) < data.size()) {
            int j = leftChild(k);
            //rightChild存在,且值小于leftChild的值
            if (j + 1 < data.size() &&
                    data.get(j).compareTo(data.get(j + 1)) > 0)
                j = rightChild(k);
            //data[j]是leftChild和rightChild中最小的
            if (data.get(k).compareTo(data.get(j)) <0)
                break;
            swap(k, j);
            k = j;
        }
    }
    //取出堆中最大的元素,替换为元素e
    public E replace(E e){
        E ret = findMin();
        data.set(0, e);
        siftDown(0);
        return ret;
    }
  //heapify操作:将数组转化为堆
   public MinHead(E[] arrs) {
        data = new ArrayList<>(Arrays.asList(arrs));
        for (int i = parent(data.size() - 1); i >= 0; i--) {
            siftDown(i);
        }
    }
    public void print() {
        for (E e : data) {
            System.out.print(" "+e);
        }
    }
    public List<E> getDate() {
        return data;
    }
    public static void main(String[] args) {
        MinHead<Integer> head = new MinHead<Integer>();
        head.add(18);
        head.add(17);
        head.add(19);
        head.add(36);
        head.add(13);
        head.add(22);
        head.add(16);
        head.add(28);
        head.add(30);
        head.add(41);
        head.add(62);
        head.print();
        System.out.println();
        head.data.set(3, 1);
        head.rebuildHead(3);
        head.print();
    }
}