priorityqueue，优先队列(PriorityQueue)
其实priorityqueue的问题并不复杂，但是又很多的朋友都不太了解优先队列(PriorityQueue)，因此呢，今天小编就来为大家分享priorityqueue的一些知识，希望可以帮助到大家，下面我们一起来看看这个问题的分析吧！
java的 的priorityqueue 默认是最小堆吗
应该是的，参考如下内容：
注意1：该队列是用数组实现，但是数组大小可以动态增加，容量无限。
注意2:此实现不是同步的。不是线程安全的。如果多个线程中的任意线程从结构上修改了列表，则这些线程不应同时访问 PriorityQueue实例，这时请使用线程安全的PriorityBlockingQueue类。
注意3:不允许使用 null元素。
注意4：此实现为插入方法（offer、poll、remove()和 add方法）提供 O(log(n))时间；
为 remove(Object)和 contains(Object)方法提供线性时间；
为检索方法（peek、element和 size）提供固定时间。
注意5:方法iterator()中提供的迭代器并不保证以有序的方式遍历优先级队列中的元素。
至于原因可参考下面关于PriorityQueue的内部实现
如果需要按顺序遍历，请考虑使用 Arrays.sort(pq.toArray())。
注意6：可以在构造函数中指定如何排序。如：
PriorityQueue()
使用默认的初始容量（11）创建一个 PriorityQueue，并根据其自然顺序来排序其元素（使用 Comparable）。
PriorityQueue(int initialCapacity)
使用指定的初始容量创建一个 PriorityQueue，并根据其自然顺序来排序其元素（使用 Comparable）。
PriorityQueue(int initialCapacity, Comparator comparator)
使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器comparator来排序其元素。
注意7:此类及其迭代器实现了 Collection和 Iterator接口的所有可选方法。
PriorityQueue的内部实现
PriorityQueue对元素采用的是堆排序，头是按指定排序方式的最小元素。堆排序只能保证根是最大（最小），整个堆并不是有序的。
方法iterator()中提供的迭代器可能只是对整个数组的依次遍历。也就只能保证数组的第一个元素是最小的。
实例1的结果也正好与此相符。
优先队列(PriorityQueue)
https://www.jianshu.com/p/94155f9616bf
在数据结构中，普通的队列是先进先出，但有时我们可能并不想有这么固定的规矩，我们希望能有一个带优先级的队列。考虑在现实生活中，一些服务排队窗口会写着“军人依法优先”；送进医院的患者，即便是按顺序到达的，生病更加严重的往往优先级也会更高；还有操作系统中的作业调度也和优先级有关......
于是我们能不能改进队列？使得队列是有一定优先级的，这样能让一些事物和任务的处理变的更加灵活。当然是可以的，最基本的我们可以基于线性结构来实现，考虑基于线性结构的时间复杂度：
1、队列是一种FIFO（First-In-First-Out）先进先出的数据结构，对应于生活中的排队的场景，排在前面的人总是先通过，依次进行。
2、优先队列是特殊的队列，从“优先”一词，可看出有“插队现象”。比如在火车站排队进站时，就会有些比较急的人来插队，他们就在前面先通过验票。优先队列至少含有两种操作的数据结构：insert（插入），即将元素插入到优先队列中（入队）；以及deleteMin（删除最小者），它的作用是找出、删除优先队列中的最小的元素（出队）。
结构\操作入队出队
普通线性结构 O(1) O(n)
顺序线性结构 O(n) O(1)
普通线性结构实现的优先队列出队时间复杂度是O(n)，因为出队要拿出最优先的元素，也就是相对最大的元素（注意：大小是相对的，我们可以指定比较规则），从而要扫描一遍整个数组选出最大的取出才行。而对于顺序线性结构的入队操作，入队后可能破坏了原来的有序性，从而要调整当前顺序。
可以看到使用线性结构总有时间复杂度是O(n)的操作，还有没有更好的实现方式呢，当然是有的，这就要来聊一聊堆Heap。
堆严格意义上来说又叫二叉堆（Binary Heap），因为它的结构是一颗完全二叉树，堆一般分为最大堆和最小堆。
堆性质：
结构性：堆是一颗除底层外被完全填满的二叉树，底层的节点从左到右填入，这样的树叫做完全二叉树。即缺失结点的部分一定再树的右下侧。
堆序性：由于我们想很快找出最小元，则最小元应该在根上，任意节点都小于它的后裔，这就是小顶堆（Min-Heap）；如果是查找最大元，则最大元应该在根上，任意节点都要大于它的后裔，这就是大顶堆(Max-heap)。
最大堆：父亲节点的值大于孩子节点的值
最小堆：父亲节点的值小于孩子节点的值
由于是完全二叉树，节点的索引之间有着一定的关系，故我们可以使用数组来存储二叉堆，具体如下：
如果从索引为0开始存储，则父亲和孩子节点的索引关系如下：
当我们需要向一个最大堆添加一条新的数据时，此时我们的堆变成了这样。
此时，由于新数据的加入已经不符合最大堆的定义了。所以我们需要对新加入的数据进行shift up操作，将它放到它应该在的位置。shift up操作时我们将新加入的数据与它的父节点进行比较。如果比它的父节点大，则交换二者。
此时我们就完成了对新加入元素的shift up操作。
当我们从堆中(也就是优先队列中)取出一个元素时。我们是将堆顶的元素弹出。(只能从堆顶取出)
此时这个堆没有顶了，那么该怎么办呢？我们只需要把这个堆最后一个元素放到堆顶就可以了。
此时我们就完成了弹出一个元素之后的shift down操作。
replace:去除最大元素后，放入一个新元素
实现：可以先extractMax,再add，两次longn操作。
实现:将堆顶的元素替换以后sift down，一次O(logn)操作
将n个元素逐个插入到一个空堆中,算法复杂度是O(nlogn),heapify的过程，算法的复杂度为O(n).
heapify:将任意数组整理成堆的形状。
首先将一个数组抽象成一个堆。这个过程，我们称之为heapify。
之后我们找到这个堆中第一个非叶子节点，这个节点的位置始终是数组的数量除以2，也就是索引5位置的27，从这个节点开始，对每一个非叶子的节点,，进行shift down操作。
27比它的子节点51要小，所以交换二者。
接下来我们看索引2位置的20。首先呢，我们需要将20与它两个子节点中较大的51交换。
每个节点堆化的时间复杂度是O(logn)，那个节点的堆化的总时间复杂度是O(nlogn)。
推导过程
堆化节点从倒数第二层开始。堆化过程中，需要比较和交换的节点个数与这个节点的高度k成正比。
所以 heapify()时间复杂度是 O(n).
建堆后，数组中的数据是大顶堆。把堆顶元素，即最大元素，跟最后一个元素交换，那最大元素就放到了下标为n的位置。
这个过程有点类似上面的“删除堆顶元素”的操作，当堆顶元素移除之后，把下标n的元素放堆顶，然后再通过堆化的方法，将剩下的n-1个元素重新构建成堆。一直重复这个过程，直到最后堆中只剩下下标为1的元素，排序就完成了。
topk和selectk问题既可以使用快排思想解决，也可以使用优先队列解决。
快排:O(n)空间O(1)
优先队列:O(nlogk)空间O(k)
优先队列的有i是，不需要一次性知道所有数据,数据流的方式处理。
【排序】堆、完全二叉树、堆排序、PriorityQueue、TopK
可以利用堆、外排序的方法来做多个处理单元的结果合并
堆，其实就是一个完全二叉树；
完全二叉树，要么是一个满二叉树，要么叶子节点层为从左到右；
堆，实际中是可以用数组实现的；
规律，把数组脑补成完全二叉树
节点 n的左孩子为 2*n+ 1,也就是 n<<1+1
节点 n的左孩子为 2*n+ 2,也就是 n<<1+2
节点 n的父节点为(n-1)/2,也就是(n-1)>>2
堆分为小根堆、大根堆
小根堆：在完全二叉树中，任何一个子树的最小值都在头部，小根堆，数组最小值在 arr[0]
大根堆：在完全二叉树中，任何一个子树的最大值都在头部，大根堆，数组最大值在 arr[0]
思想：1、根据大根堆的特点，先将一个数组构建成为一个大根堆，这样堆顶就是最大的
2、再将堆顶和最后一个数互换，将最大的数放到最后，随即调整维持大根堆
继续互换、调整。
java实现的堆结构、优先级队列， PriorityQueue()
PriorityQueue当size达到了初始的initialCapacity容量后会进行扩容，每次容量加1。
1->1
1,2->1.5
1,2,3->2
...
准备一个大根堆，一个小根堆
把小于等于大根堆对顶的树插入大根堆，
把大于大根堆对顶的树插入小根堆；
同时，要调整大根堆和小根堆的数量，数量差值不要超过1；
如果大根堆的size大了，就把大根堆的堆顶取出插入小根堆；
如果小根堆的size大了，就把小根堆的堆顶取出插入大根堆；
这样就能达到，大根堆，小根堆数量保持平衡，同时大根堆中的小的n/2个数，小根堆中是大的n/2个数，
（大根堆堆顶+小根堆堆顶）/2就是流的中位数
假设我们有 100个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。我们希望将这些 100个小文件合并成一个有序的大文件。
思路：利用一个小根堆，把每个文件的第一条记录取出来，放入小根堆中，那么小根堆的堆顶就是这100条记录中顺序最小的记，它为记录A，也是这100个文件中顺序最小的，将这个堆顶追加到准备的大文件。从记录A原来所在的文件中再取出一条记录，放入小根堆，取出堆顶，如此重复...
思路：利用一个size为k的堆，求最大的Top K用小根堆，求最小的Top k用大根堆。
我们可以维护一个大小为 K的小顶堆，顺序遍历数组，从数组中取出取数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K大数据了。
遍历数组需要 O(n)的时间复杂度，一次堆化操作需要 O(logK)的时间复杂度，所以最坏情况下，n个元素都入堆一次，所以时间复杂度就是 O(nlogK)。
使用map<key,count>计数，count放入小根堆中，多个小根堆合并求top10.
分析：假设一条搜索50个字节，10亿条那么就占用了50GB的大小，所以一次对所有数据进行统计是不可行的。
0、准备10个空文件
1、采用hash算法将日志进行计算之后得到hash值，模10，存放入对应的文件中。那么每个文件大概会有1亿条记录，假设平均每条关键词重复10次，那么就是1000万条关键词，大概500MB，1G的内存是可以存下的
2、使用hashmap对每个小文件中的关键词进行数量统计，对每个小文件的统计的结果存入一个Size为10的小根堆。
3、对这10个小根堆再进行合并得到最终的Top 10的搜索关键词
推荐阅读：
数据结构和算法|堆的应用
好了，文章到这里就结束啦，如果本次分享的priorityqueue和优先队列(PriorityQueue)问题对您有所帮助，还望关注下本站哦！