- 什么是优先队列
- 常用方法
- 最小优先队列
- 最大优先队列
- 注意
普通的队列都是先入先出的形式，元素在队尾加入，在队头删除。优先队列中，元素被赋予优先级，具有最高优先级的元素先出。通常采用二叉堆结构实现。
所以优先队列和堆一样，有两种形式：最大优先队列和最小优先队列。
最大优先队列是指最大值具有最高优先级。
最小优先队列是值最小值具有最高优先级。
每次的push和pop操作，队列都会动态的调整。
Java中PriorityQueue类实现优先队列。
public boolean add(E e)；//在队尾添加元素 public E peek();//取出队头元素 public boolean remove(Object o)；//删除指定元素 public boolean contains(Object o)；//检查是否包含元素 public Object[] toArray()；//将队列转换成数组 public int size()；//返回元素个数 public void clear() ；//清空队列 public E poll()； //返回并清除队头元素 public boolean isEmpty(); //判断队列是否为空最小优先队列
public class test {
@Test
public void test() {
int[] nums = new int[] { 12, 3, 8, 5, 16, 30, 9 };
Queue queue = new PriorityQueue<>();
for (int num : nums) {
queue.add(num);
}
System.out.println(Arrays.toString(queue.toArray()));
while (!queue.isEmpty()) {
System.out.print(queue.poll() + " ");
}
}
}
结果：
[30, 12, 16, 3, 5, 8, 9] 30 16 12 9 8 5 3最大优先队列
public class test {
@Test
public void test() {
int[] nums = new int[] { 12, 3, 8, 5, 16, 30, 9 };
Queue queue = new PriorityQueue<>(new Comparator() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for (int num : nums) {
queue.add(num);
}
System.out.println(Arrays.toString(queue.toArray()));
while (!queue.isEmpty()) {
System.out.print(queue.poll() + " ");
}
}
}
结果：
[30, 12, 16, 3, 5, 8, 9] 30 16 12 9 8 5 3注意
- 优先队列默认是最小优先队列，要使用最大优先队列可以重写Comparator接口
- 不是放入优先队列里数字就是有序的，只是队头元素永远是最大值或最小值
