版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_43126117/article/details/96994418
我们先回忆一下什么是队列,队列,一种先进先出的数据结构。主要关注点在于先入的元素先出。
队列
我们先看一下百度百科关于优先队列的介绍
在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。
在普通队列的基础上,在添加元素进队列之前,就已经为元素设置好优先级,这个优先级可以是最大值、最小值、出现次数、达到某个限度的因数等等。
军训排队,最矮的在前面,最高的在后面。
电脑操作系统(window10),交互功能的进程优先级高。
生活工作中,自己感觉重要的事情先做。
这些我们编排好优先级的事情,不管入队的顺序如何,都是优先级高的先出队。
堆(二叉堆、多项式堆、斐波拉契堆...)
二叉搜索树
优先队列的实现有很多种,常见的就是上面这几种,后面会给出实现的详细介绍。
先看一下Java中优先队列的继承体系和实现方法吧。
优先队列也是继承抽象队列,实现队列接口,那么也就有接口中规定的方法了呗(add、offer、clear、poll、peek...)
我们进一步观察源码发现,Java中优先队列是基于最小堆,是一个完全平衡二叉树。通过传递一个comparator或者collection对象,可以实现自定义优先级。下面,我们通过源码来看看添加方法。
package java.util.PriorityQueue;
public boolean offer(E e) { //添加方法
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length) //判断size是否大于数组
grow(i + 1); //数组自动扩容
size = i + 1;
if (i == 0)
queue[0] = e; //根节点
else
siftUp(i, e); //传递数组下标和元素
return true;
}
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x); //传入了比较器的
else //默认比较器
siftUpComparable(k, x);
}
private void siftUpComparable(int k, E x) { //默认比较器
Comparable<? super E> key = (Comparable<? super E>) x; //拿到当前元素x的比较器
while (k > 0) { //迭代
int parent = (k - 1) >>> 1; //无字符移位运算符,k为正数,相当于>>1 ,也就是除2.
Object e = queue[parent]; //获取父节点元素
if (key.compareTo((E) e) >= 0) //调用当前元素比较器,当前节点大于父节点,则停止迭代,保存当前元素到下标为K的数组
break;
queue[k] = e; //把父节点保存在下标为K的数组中
k = parent; //把刚刚父节点的下标保存在K中
}
queue[k] = key; //迭代结束 , 保存当前元素到特定下标的数组中
}
//假如存入的元数是整型,这个整型的比较器如下
package java.lang.Integer;
public int compareTo(Integer anotherInteger) {
return compare(this.value, anotherInteger.value);
}
public static int compare(int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}
这就是Java中内置的优先队列的offer方法,通过调用传入元素的比较器,与父节点比较,再次迭代,进而决定元素存储下标,最后保存到数组中。
如果调用的是poll方法,那么运行过程思路如下:先获取下标为0的数组元素和再次堆化(即,再次的运用比较器,生成有根节点的树)。这个小顶堆只是确保最小值在数组[0]位上,其他元素的大小位置是不一定的,只有每次入队出队,再通过比较器,把最小值移动到数组[0]上。