本文共 2324 字，大约阅读时间需要 7 分钟。

public class BinaryHeap<AnyType extends Comparable<? super AnyType>> {     private static final int DEFAULT_CAPACITY=10;     private int currentSize;     private AnyType[] array;     public BinaryHeap(){         currentSize=0;         array=null;         enlargeArray(DEFAULT_CAPACITY);     }     /*      * 构造一个二叉堆，并且有一些项的集合      */     @SuppressWarnings("unchecked")     public BinaryHeap(AnyType[] items){         currentSize=items.length;         array=(AnyType[])new Comparable[(currentSize+2)*11/10];         int i=1;         for(AnyType item:items){             array[i++]=item;         }         buildHeap();     }     /*      * 进行排序      */     private void buildHeap(){         for(int i=currentSize/2;i>0;i--){             percolateDown(i);         }     }     /*      * 用于扩容的函数      */     private void enlargeArray(int newSize){         @SuppressWarnings("unchecked")          AnyType[] newArray=(AnyType[])new Comparable[newSize];//这里我本来new了一个Object，发现报错，因为不能new泛型，我就改成接口了缺，通过了，可以解释吗         AnyType[] old=array;         if(old!=null){             for(int i=0;i<old.length;i++){                 newArray[i]=old[i];             }         }         array=newArray;     }     /*      * 把第hole位置的元素，放到合适的位置      */     private void percolateDown(int hole){         int child;         AnyType tmp=array[hole];//得到当前位置的值         for(;hole*2<=currentSize;hole=child){//如果当前节点还有左孩子的话             child=hole*2;//得到左孩子             //如果当前孩子不等于size则说明还有右孩子，就比较左右孩子的大小，找到小的孩子，可以上移             if(child!=currentSize&&array[child+1].compareTo(array[child])<0){                 child++;             }             //如果当前小的那个孩子比当前值要小的话就上移，然后继续循环             if(array[child].compareTo(tmp)<0){                 array[hole]=array[child];             }else {//如果当前值比小的那个值还要小的话，就把当前值存在这个地方就可以了                 break;             }         }         array[hole]=tmp;     }     /*      * 插入数据      */     public void insert(AnyType x){         if(currentSize==array.length-1)             enlargeArray(array.length*2+1);         int hole=++currentSize;         //把新插入的元素和最后一个节点的父亲节点比大小，如果比他小那个父亲节点就下移，         //一直到比他大，就把值插入当前位置。         for(array[0]=x;x.compareTo(array[hole/2])<0;hole/=2)             array[hole]=array[hole/2];         array[hole]=x;     }     /*      * 删除最小元      */     public AnyType deleteMin(){         if(isEmpty()){             throw new UnsatisfiedLinkError();         }         AnyType minItem=findMin();//只要把根节点的值给他就好了，就是坐标为1的值         array[1]=array[currentSize--];//把最底端的值给第一个元素         percolateDown(1);//然后执行这个收入的插入         return minItem;     }     public boolean isEmpty(){         return currentSize==0;     }     private AnyType findMin(){         return array[1];     }

}

测试：

    public static void main(String[] args) {

        // TODO Auto-generated method stub         BinaryHeap<Integer> binaryHeap=new BinaryHeap<>();         binaryHeap.insert(1);         binaryHeap.insert(5);         binaryHeap.insert(4);         binaryHeap.insert(2);         binaryHeap.insert(7);         while(!binaryHeap.isEmpty()){             System.out.println(binaryHeap.deleteMin());         }     }

效果：

1

2 4 5 7

转载地址：http://wtjqi.baihongyu.com/