《Java数据结构与算法》笔记-CH4-6优先级队列

/**
 * 优先级队列 
 * 效率：插入O(n),删除O(1).第12章介绍如何通过堆来改进insert时间
 */
class PriorityQueue {
private int maxSize;
private long[] pQueue;
private int nItems;

public PriorityQueue(int size) {
maxSize = size;
pQueue = new long[maxSize];
nItems = 0;
}

/**
 * insert 
 * 先检查队列中是否有数据项，
 * 如果没有，就插入到下标为0的单元里。 
 * 否则从数组顶部开始向上移动存在的数据项，直到找到新数据项应该插入
 * 的位置，然后插入新数据项，并把nItems加一。
 * 
 * @param item
 */
public void insert(long item) {
int j;
if (nItems == 0)// 如果队列为空，直接插入，个数+1
pQueue[nItems++] = item;
else {// 如果队列不空，找到要插入的位置
for (j = nItems - 1; j >= 0; j--) {
// 如果插入项大于当前，当前项上移一个位置
if (item > pQueue[j])
pQueue[j + 1] = pQueue[j];
else// 找到要插入的位置，跳出循环
break;
}
pQueue[j + 1] = item;
nItems++;
}
}

public long remove() {
return pQueue[--nItems];
}

public long peekMin() {
return pQueue[nItems - 1];
}

public boolean isEmpty() {
return nItems == 0;
}

public boolean isFull() {
return nItems == maxSize;
}
}

public class PriorityQueueDemo {
public static void main(String[] args) {
PriorityQueue pq = new PriorityQueue(5);
pq.insert(4);
pq.insert(2);
pq.insert(5);
pq.insert(7);
pq.insert(3);
System.out.println(pq.remove());
System.out.println(pq.remove());
System.out.println(pq.remove());
System.out.println(pq.remove());
}
}