数据机构之优先级队列

爱被打了一巴掌 2022-08-11 04:29 109阅读 0赞

package com.zhiru;
    /*
     * 优先级队列例子
     * 基于数组实现
     * ----------------------------
     * 编号     1     2    3   4    5
     * 优先权20    0    10  30   15//值小的优先权大
     * 顺序    2     3    5   1    4
     */
    public class PQueue {
    
    	private int count=0;//队列元素个数
    	private int maxSize=100;//队列元素最大容量
    	private int[]data;
    	PQueue(int size){
    		maxSize=size;
    		data=new int[maxSize];
    	}
    	public boolean isEmpty(){
    		return count==0;
    	}
    	public boolean isFull(){
    		return count==maxSize;
    	}
    	public int getSize(){
    		return count;
    	}
    	//将元素插入到队尾
    	public void insert(int val){
    		if(count<=maxSize){
    			data[count++]=val;
    			//插入后调整，保证权值大的在后面，即优先权大的在前面。
    			adjust();
    		} 
    		else
    			System.out.print("队列满了\n");
    			
    	}
    	//在插入一个元素后将队列进行调整，将优先权大（权值小）的调到队头.
    	//类似插入排序算法.
    	public void adjust(){
    		if(count<=maxSize){
    			int temp=data[count-1];
    			for(int j=count-2;j>=0;j++){
    				if(data[j]<=temp)
    					break;
    				else
    					data[j+1]=data[j];//元素后移.
    				data[j+1]=temp;//找到合适的位置插入.
    			}
    			
    		}
    	}
    	//返回队头元素.
    	public int getMin(){
    		if(count==0) return -1;//表示队空.
    		int x=data[0];
    		for(int i=1;i<count;i++) data[i-1]=data[i];//前移删除队头元素.
    		count--;//长度减一
    		return x;
    	}
    	public void printPqueue(){
    		for(int j=0;j<count;j++){
    			System.out.print(data[j]+" ");
    		}
    		System.out.print("\n");
    	}
    	public static void main(String[]args){
    		PQueue pq=new PQueue(5);//maxSize=;
    		int[]x={20,0,10,30,15};
    		for(int i=0;i<x.length;i++){
    			pq.insert(x[i]);
    		}
    		pq.printPqueue();
    		pq.getMin();
    		pq.printPqueue();
    		
    	}
    }

20 0 10 30 15   
0 10 30 15