Java数据结构与算法之优先级队列

缺乏、安全感 2022-08-09 15:59 166阅读 0赞

同样，直接上代码

package com.wayne.example.MyPriorityQueue.PriorityQ;
    /* * 1， 队列特性：数据项按关键字的值有序，关键值最小的数据项总在队头。 * 2， 优先级队列通常是使用堆的数据结构来存储。 * 3， 优先级队列的效率： * a) 插入操作需要O(N)的时间； * b) 删除操作需要O(1)的时间。 */
    public class MyPriorityQueue { 
        /* * 优先级队列的三个要素 * 队列预计长度 maxSize * 队列的类型 int[] queArray * 队列的个数 nItems */
        private int maxSize;
        private int[] queArray;
        private int nItems;
    
        /** * 初始化长度为length的空的优先级队列 * @param length 队列的长度 */
        MyPriorityQueue(int length){
            maxSize = length;
            queArray = new int[maxSize];
            nItems = 0;
        }
    
        /** * 向该队列中插入元素 * @param i 待插入的元素 */
        public void insert(int i){
            if(nItems == 0){
                queArray[nItems] = i;
            }
            else{
                int index;
                for(index = nItems-1;index>=0;index--){
                    if(i>queArray[index]){
                        queArray[index+1] = queArray[index];
                    }
                    else
                        break;
                }
                queArray[index+1] = i;
            }
            nItems++;
        }
    
        /** * 删除优先级队列的元素 * @return 返回删除的值 */
        public int remove(){
            return queArray[--nItems];
        }
    
        /** * 判断优先级队列是否为空 * @return 如果为空，则返回true;如果不为空，则返回false; */
        public boolean isEmpty(){
            return nItems == 0;
        }
    
        /** * 判断优先级队列是否满 * @return 如果满，则返回true;如果不满，则返回false */
        public boolean isFull(){
            return nItems == maxSize-1;
        }
    }

测试用例

package com.wayne.example.MyPriorityQueue.PriorityQ;
    
    public class MyPriorityQueueApp {
    
        public static void main(String[] args) {
            MyPriorityQueue myPriorityQueue = new MyPriorityQueue(5);
    
            myPriorityQueue.insert(3);
            myPriorityQueue.insert(6);
            myPriorityQueue.insert(1);
            myPriorityQueue.insert(7);
            myPriorityQueue.insert(2);
    
            while(!myPriorityQueue.isEmpty())
                System.out.println(myPriorityQueue.remove());
        }
    
    }