如何用O（logN）排序具有n个元素的优先级队列？
马里奥斯·阿斯
我有一个由用户指定的整数流和一个int k。在程序结束时，我必须打印k个最高的数字。我只允许使用容量为k的优先级队列。
我的问题是，当队列达到最大容量时，下一个整数读取必须替换队列中的最小整数。
如何在插入后对队列进行排序，以使我知道在下一次迭代中要替换哪个int，且复杂度为O（logn）？我使用了一个游泳方法（在下面显示），但是，尽管它将新的int放置在正确的级别，但是它不能使队列完全排序。
这是游泳方法：
private void swim(int i){
while (i > 1) { //if i root (i==1) return
int p = i/2; //find parent
int result = cmp.compare(heap[i], heap[p]); //compare parent with child
if (result == 1) return; //if child <= parent return
swap(i, p); //else swap and i=p
i = p;
}
}
为了使自己更清楚，这里有一个k = 3的例子。
1: A = 42 / B = null / C = null
2: A = 69 / B= 42 / C = null (69 swims upwards)
3: A = 69 / B= 42 / C = 32
4: A = 69 / B= 42 / C = 32 (no change)
5: A = 104 / B= 42 / C = 69 (104 is inserted replacing 32, then swims upwards)
6: A = 104 / B= 42 / C = 93 (93 is inserted replacing 69, remains there)
极客程序员
首先，您无法保持PriorityQueue排序顺序；如果与堆数据结构不完全相同，则它是相似的。
PriorityQueue只是被授予者，根据其最小或最大堆，顶部元素是最小或最大。
而且，您还会对2个不同的问题感到困惑，即对元素进行排序和查找K个最大/最小元素。
如果要对N个元素的给定列表中的元素进行排序：使用基于比较的排序算法，运行时间不会比O（N * log（N））更好。
但是，如果您的情况只是从N个元素的列表中查找K个最小/最大元素：您可以在O（N * log（K））时间内实现。
请检查一次此问题：查找数组中的前n个最大元素
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
对具有较高优先级的一系列元素和具有较低优先级的其他元素的优先级队列进行排序
- 2
具有两个优先级Python的优先级队列
- 3
具有两个优先级值的优先级队列
- 4
具有两个优先级Python的优先级队列
- 5
如何在C ++中定义具有四个值的优先级队列？
- 6
如果多个元素具有相同的优先级，Python中是否有“ Lifo”类型的优先级队列？
- 7
Dijkstra的最短路径算法，具有部分排序的树作为优先级队列
- 8
如何以恒定步长填充数组元素之间的间距，并结合具有优先级和次要优先级的两个这样的数组？
- 9
如何在Java中实现元组的优先级队列，该队列使用具有不同类型的两个字段进行排序？
- 10
具有减少键操作的Javascript优先级队列
- 11
具有自定义顺序的优先级队列
- 12
创建具有相反顺序的优先级队列
- 13
如何获取优先级队列的最后一个元素而不遍历它
- 14
如何在Scala中获取优先级队列的第k个最小元素？
- 15
如何将元素移出STL优先级队列
- 16
用Java排序优先级队列
- 17
C ++优先级队列-排序间隔
- 18
C ++优先级队列未排序
- 19
基于元素字段具有元素唯一性的优先级队列的数据结构
- 20
如何对列表列表进行排序以保留具有最高优先级的项目？（Python）
- 21
C ++实现具有不同优先级功能的优先级队列的最佳方法是什么？
- 22
Java优先级队列如何工作？
- 23
如何删除STXXL优先级队列？
- 24
此优先级队列如何工作？
- 25
最小优先级队列和最大优先级队列未正确排序
- 26
如何在具有特定优先级列表的元素之间进行选择？
- 27
如何从java中的队列中删除特定元素（不是优先级队列）
- 28
如何使用两个队列实现优先级队列
- 29
如何使用两个队列实现优先级队列
我来说两句