堆的Java实现

一.概念

堆是计算机科学中一类特殊的数据结构的统称，堆通常可以被看做是一棵完全二叉树的数组对象。
堆的特性：

它是完全二叉树，除了树的最后一层结点不需要是满的，其它的每一层从左到右都是满的，如果最后一层结点不是满的，那么要求左满右不满。保证叶结点只能出现在最下层or次下层
快速辨别：看最后一层的最后一个结点G，G之前是满的就是完全二叉树。而红色的树 G之前未满，则是不完全二叉树
它通常用数组来实现。具体方法就是将二叉树的结点按照层级顺序放入数组中，根结点在索引位置1处(舍弃索引0)，它的子结点在位置2和3，而子结点的子结点则分别在位置4,5,6和7，以此类推。

抛弃0号索引，从1开始存更方便！

规律：
①如果一个结点的位置为k，则它的父结点的位置为k/2 ,
②而它的两个子结点的位置则分别为2k和2k+1。
这样，在不使用指针的情况下，我们也可以通过计算数组的索引在树中上下移动：从a[k]向上一层，就令k等于k/2,向下一层就令k等于2k或2k+1。
③每个结点的key值都大于等于它的两个子结点。
这里要注意堆中仅仅规定了每个结点大于等于它的两个子结点，但这两个子结点的顺序并没有做规定，跟我们之前学习的二叉查找树不一样！。 堆并不是完全有序的 !
其中最大的元素就放在索引1处（舍弃索引0 ，从索引1开始放元素）

二.实现

insert()插入方法的实现
堆是用数组完成数据元素的存储的，由于数组的底层是一串连续的内存地址，所以我们要往堆中插入数据，我们只能往数组中从索引1处开始，依次往后存放数据，但是堆中对元素的顺序是有要求的。
每一个结点的数据要大于等于它的两个子结点的数据， 所以每次插入一个元素，都会使得堆中的数据顺序变乱，这个时候我们就需要通过一些方法让刚才插入的这个数据放入到合适的位置。

swim()方法逻辑：比较新添加的元素k和他的父节点的大小，如果k大于他的父节点，则交换k和他的父节点的位置；交换完后再将k和他的父节点进行比较… 直到k不再大于他的父节点

delMax删除最大的元素的实现
由堆的特性我们可以知道，索引1处的元素，也就是根结点就是最大的元素，当我们把根结点的元素删除后，需要有一个新的根结点出现，这时我们可以暂时把堆中最后一个元素放到索引1处，充当根结点，但是它有可能不满足堆的有序性需求，这个时候我们就需要通过一些方法，让这个新的根结点放入到合适的位置，然后通过下沉sink()方法对堆的顺序进行调整。

sink()方法逻辑：求出当前结点左右子节点的最大值max，若当前结点小于max就将当前结点和max进行交换。

代码：

public class heap <T extends Comparable<T>>{
        private T[] items;
        private int N;

        public heap(int capacity){
            this.items= (T[]) new Comparable[capacity+1]; // comparable类
            this.N=0;
        }  //数组是定长的，要先指定初始容量

        private boolean more(int i,int j){ //比较i索引的key是否小于j索引处的key
            return ( items[i].compareTo(items[j])>0 );
        }

        private void swap(int i,int j){ //交换
            T temp=items[i]; //临时变量
            items[i]=items[j];
            items[j]=temp;
        }


        public void insert(T t){
            items[++N]=t;  //先让N+1 ，就可以废弃掉0索引，同时元素的个数也是正确的
            swim(N); //让N索引处的值通过上浮放到合适的位置
        }

        public T delMax(){  //删除最大元素即根结点
            T max= items[1]; //记录根结点
            //交换根节点max和 索引最大处的元素
            swap(1,N);
            //将根节点放到索引N处即删掉最大索引处的元素，即交换后的根节点max
            items[N]=null;
            N--;

            //从新的根节点开始，使用下沉sink方法
            sink(1);
            return max; //只是返回要被删除的元素
        }


        private void  swim(int k){  //上浮算法,使索引k处的元素处于一个正确的位置
        //通过循环不断和父节点进行比较，大于父节点则和父节点交换，
        while(k>1){
            //比较当前结点和父节点
            if(more(k,k/2)){ //如果当前结点k大于 其父k/2，则交换
                swap(k,k/2);
            }
            k=k/2; //当不满足if，k会越来越小直到跳出while
        }


        }

    private void sink(int k) {   //下沉算法，使索引k处的元素处于一个正确的位置
        //通过循环对比， 如果当前结点元素 < 两个子节点中较大值，则交换
        int max;//记录较大元素的索引

        while ( (2*k <=N) { //循环条件： 节点k存在左子节点
        //获取两个子节点中的最大值记录为max，再将k节点和max比较，若大于max则不需要下沉
            if (2 * k + 1 <= N) { //有左子结点且有右子结点
                if (more(2 * k, 2 * k + 1)) { //如果左子结点大于右子节点
                    max = 2 * k;
                } else {
                    max = 2 * k + 1;
                }
            } else {
                max = 2 * k; //只有左子节点，没有右子节点直接让max为左子节点
            }
            if (more(k, max)) {
                break; //当前k结点大于 左右子节点中最大结点，则不需要交换，循环结束
            } else {  //k节点小于max，则需要继
                swap(k, max);
                k = max; //变换k的值
            }
        }

    }


    public static void main(String[] args) {
        heap<String> h=new heap<String>(12);
     	p.insert("E");
        p.insert("B");
        p.insert("F");
        p.insert("G");
        p.insert("D");
        p.insert("C");
        p.insert("A");

        //通过循环从堆中删除数据
        String result=null;
        while(   (result=h.delMax())  !=null){ //循环条件：只要还有数据可删
            System.out.println(result+" ");  //每次删除掉的都是最大的元素
        }
    }
}