优先队列算法

妖狐艹你老母 2022-06-18 05:19 261阅读 0赞

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