「优先队列」

应用场景:从序列中找一个最值(最大值或最小值),如果顺序寻找最值需要O(n)的时间,而使用优先队列则只需要O(logn)的时间。

普通的队列是一种先进先出的数据结构,元素在队尾入,在队头出。

在优先队列中。元素被赋予了优先级,具有最高优先级的元素先出。

优先队列是利用堆来实现的,堆可以看作是一棵完全二叉树的循序存储结构,具有n个节点的完全二叉树的深度为(logn)+1

在这棵完全二叉树中,

如果每一个节点的值都大于等于左右孩子的值,则称之为最大堆,大顶堆。

如果每一个节点的值都小于等于左右孩子的值,则称之为最小堆,小顶堆。

优先队列的操作

出队:堆顶出队,最后一个记录代替堆顶的位置,重新调整为堆

出队后,除了堆顶之外,其他节点都是满足最大堆的定义,只需要将堆顶执行“下沉”操作,即可调整为堆。

下沉:

堆顶与左右孩子比较,

如果比孩子大,则已满足堆;

如果比孩子小,则与较大的孩子交换,交换到新的位置后,继续向下比较,从根结点一直比较到叶子。

入队:新纪录放入最后一个记录之后,重新调整为堆。

入队后,除了新入队记录外,其他节点都满足最大堆的定义,只需要将新纪录执行“上浮”操作,即可调整为堆。

上浮:

新纪录与其双亲比较,

如果小于等于双亲,则已满足堆;

如果比双亲大,则与双亲交换,交换到新的位置后,继续向上比较,从叶子节点一直比较到根。

JDK

PriorityQueue

  • PriorityQueue是基于二叉堆原理的优先队列,队列用动态数组实现。
  • 它是非阻塞的、非线程安全的;

PriorityQueue内部维护了几个重要属性:

类型含义
queueObject[]代表PriorityQueue的队列,存放元素
sizeint当前队列包含元素个数
comparatorComparatorPriorityQueue根据比较器对元素优先级排序
modCountint记录队列被修改的次数

使用:

jdk默认使用的是小顶堆

public static void main(String[] args) {
   PriorityQueue<String> queue = new PriorityQueue<>();
   queue.add("hello");
   System.out.println(queue.peek());
   queue.remove("hello");
   System.out.println(queue.peek());
}

大顶堆:

PriorityQueue<Integer> pq = new PriorityQueue<>(nums.length, new Comparator<Integer>(){
     @Override
     public int compare(Integer o1, Integer o2) {
         return o2 - o1;
     }
});

PriorityBlockingQueue

  • PriorityQueue线程安全版本
  • 同样是基于二叉堆的原理,用动态数组实现
  • 阻塞的、线程安全的
  • 使用ReentrantLock保证线程安全

DelayQueue

  • 基于PriorityQueue实现的延迟队列

  • 它的删除、插入操作和PriorityQueue基本一致,主要的区别在与poll()、take()等方法。PriorityQueue是只要队列首部有数据就除移,而DelayQueue还需要判断是否达到除移的时间。

  • 至于take()、poll()方法的区别在于,take()会阻塞,而poll()直接返回。

评论