优先级队列

心已赠人 2022-07-18 00:26 280阅读 0赞

## 前面说过普通队列以及循环队列的使用。关于队列还有一种常用的数据结构：优先级队列。先来看一下下面实际背景： ##

## 在办公的时候，桌面上会有一堆需要处理的文件。但是事有轻重缓急，实际情况决定了哪些事情必须先处理，有些事情可以推迟到以后处理。这样就可以把马上处理的事情写在计划表的最前面（该事件优先级最高），其他优先级低的事件可以往后排。如果把计划安排表看做是一个队列吗，这样就形成了一个优先级队列。 ##

## 关于优先级队列，数据项按照关键字的值有序，这样能保证关键字最小的数据项总是在对头。数据项的插入会按照顺序插入到合适的位置以保证队列的顺序。通常来说具有最小关键字值得数据项具有较高的优先级。（通常这么认为） ##

## **优先级队列的描述** ##

## 最小关键字的数据项总是在数据的高端（最高下标值处），而且最大的数据项总是在下标值为0的位置上。如下图所示： ##

![这里写图片描述][20160902231009967]

## 通常优先队列有Insert数据、remove等操作。下面给出相关代码： ##

class PriorityQuene
    {
        private int nItem=0;
        private int maxSize=0;
        int[] priorityQ=null;
        public PriorityQuene(int n)
        {
            this.maxSize=n;
            priorityQ=new int[n];
        }
    }

## **向优先级队列加入数据** ##

//insert data
        public void insret(int data)
        {
            int i=0;
            if(nItem==0)
            {
                //从0开始插入数据
                priorityQ[nItem++]=data;
            }else
            {
                for(i=nItem-1;i>=0;i--)
                {
                    if(priorityQ[i]<data)//新数据大于最低端数据
                    {
                        priorityQ[i+1]=priorityQ[i];
                    }
                    else
                    {
                        break;
                    }
                }
                priorityQ[i+1]=data;//插入数据
                nItem++;
            }
        }

## 以上代码是确定队列是一个具备优先级队列的重要环节。本质是插入排序。可以从之前所说的插入排序中受到启发。 ##

## 从优先级队列中删除数据。remove相比就没这么复杂了，从队列的head删除数据即可。 ##

public int remove()
        {
            return priorityQ[--nItem];
    
        }

## 查看最高优先级的数据以及对优先级队列的一些full、empty判断. ##

public int peekMin()
        {
            return priorityQ[nItem];
        }
        public boolean isFull()
        {
            //System.out.println("优先队列已经满了");
            return (nItem==maxSize);
        }
        public boolean isEmpty()
        {
            //System.out.println("优先队列为空");
            return (nItem==0);
        }

## 在主main里面进行测试 ##

public static void main(String[] args) {
            // TODO Auto-generated method stub
            PriorityQuene pq=new PriorityQuene(6);
            while(!pq.isFull())
            {
                pq.insret(30);
                pq.insret(50);
                pq.insret(10);
                pq.insret(40);
                pq.insret(20);
                pq.insret(60);
            }
    
            //pq.insret(10);
            while(!pq.isEmpty())
            {
                System.out.println(pq.remove());
            }
    
        }

## 测试输出是： ##

10
    20
    30
    40
    50
    60

## 这与优先级队列的要求相一致。 ##

## **关于优先级队列的效率** ##

## 以上实现的优先级队列插入操作需要O（N）时间，remove操作需要O(1)时间。 ##

[20160902231009967]: /images/20220717/e6079ca07ff3497f8f4b4d1e745743ce.png