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

同样，直接上代码

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());
    }

}