优先队列即堆：插入算法与删除算法JAVA

深碍√TFBOYSˉ_ 2022-06-08 05:37 178阅读 0赞

首先介绍下，优先队列的信息。里面有一个数组，0位置不存元素。1位置开始存，第i个元素，左孩子是2i，右孩子是2i+1，父节点是i/2。还有就是根据优先队列的插入算法，所以都是先有左孩子，再有右孩子的。

代码来自[数据结构][Link 1]与[算法][Link 1]分析（[Java][]语言）上面给出的代码，主要是注释有用。

插入算法（上滤）：

public void insert( AnyType x )
        {
            if( currentSize == array.length - 1 )
                enlargeArray( array.length * 2 + 1 );
    
                // Percolate up
            int hole = ++currentSize;
            for( array[ 0 ] = x;hole > 1 && x.compareTo( array[ hole / 2 ] ) < 0; hole /= 2 )
                array[ hole ] = array[ hole / 2 ];
            array[ hole ] = x;
        }

循环条件里，必须有hole>1,因为当hole等于1时，就不应该进入循环了，因为这时已经判断出了插入值比hole=1的位置即根节点还要小了。

删除算法（下滤）：

public AnyType deleteMin()
    {
    	if(isEmpty())
    		throw newUnderflowException();
        AnyType minItem=findMin();//找到最小元，即在数组位置1上的元素
        array[1]=array[currentSize--];//直接把最大元替换掉最小元，大小减一
        percolateDown(1);//下滤从1开始
        //算法其实就是要给最大元从新找个可以放入的位置
        return minItem;
    
    }
    
    private void percolateDown(int hole)
    {
    	int child;
    	AnyType tmp=array[hole];//因为传进来的是1，所以就是把替换来的最大元放进tmp里
    
    	for( ; hole*2 <= currentSize ; hole = child )//只要当前hole的左孩子小于size，即存在左孩子
    	{
           child=hole*2;//把child赋值为左孩子索引
           if(child!=currentSize && array[child+1].compareTo(array[child]<0))//只要当前左孩子不是最大索引，即当前hole还有个右孩子
            //而且右孩子的值比左孩子的值大
           	child++;//就把当前child的值变为右孩子，即child的值肯定为左右孩子中最大孩子的那个索引
           if(array[child].compareTo(tmp)<0)//如果child的值比tmp小，那么就得下滤，把child的值赋值给hole，再把child变成新的hole
           	array[hole=array[child]];
           else 
           	break;
    	}
    
    	array[hole]=tmp;//如果跳出循环，到了这步，说明当前hole是可以将最大元放入的位置了
    }

[Link 1]: http://lib.csdn.net/base/datastructure
[Java]: http://lib.csdn.net/base/java