标签：优先 队列 int 算法 child AnyType array hole currentSize
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
标签：优先,
队列,
int,
算法,
child,
AnyType,
array,
hole,
currentSize
From： https://blog.51cto.com/u_12026373/5930816