【基础】PriorityQueue

1. 初识PriorityQueue

PriorityQueue 是队列,队列就是先进先出, 但PriorityQueue 能做到按优先级出队列。
PriorityQueue 实现Queue接口,但如何做到按优先级出队列?
在数据结构上,采用堆,在数据存储上采用的是数组;

通过在入队时,就把数据排序好;排序就是用户自定义优先级。
在出队时,通过堆这种结构,出队堆顶元素,并重新维护好堆的数据结构。

2. 应用场景:Top K 元素

小顶堆:求k个最大数
构建的是指定容量的小顶堆,因此每次queue.peek()返回的是最小的数字,在遍历数组的过程中,如果遇到比该数字大的元素就将最小的数字poll(移除掉),然后将较大的元素添加到堆中,在添加进去堆中的时候,堆同时会按照优先级比较,将最小的元素再次放到堆顶,这样的做法就是会一直保持堆中的元素是相对较大的,同时堆顶元素是堆中最小的。
大顶堆:求k个最小数
直接构建一个大顶堆,这样元素最大的值在堆顶,每次去和数组的元素的值去做比较,只要堆顶元素比数组的值小,就将堆顶元素poll出来,然后将数组的值添加进去,这样就可以一直保持集合数组中一直是最小的k个数字。

3. 应用场景:TopK 高频元素

先计算数组中数字出现的频率,然后维护一个哈希表用来存储元素的频率;
然后构建优先级队列,这里依旧是构建小顶堆,不过因为该题是计算元素出现的频率,因此我们需要将每个元素的频率值做对比

参考

如何解决TOP-K问题

Published by

风君子

独自遨游何稽首 揭天掀地慰生平

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注