algorithm - 优先队列随机访问

Question

我有优先级队列，它按某个值对元素进行排序(让它命名为评级)。我需要按评级从队列中取出元素。所以我需要实现函数queue_get(rating)。此功能还可以增加优先级堆的评级。

但问题是堆的每一层都不是按等级排序的。每一层的元素只满足堆的性质。所以我不能肯定地通过评级返回第 N 个元素。

是否有具有此类功能的优先级队列的实现？我应该使用其他数据结构吗？

Answer 1

最简单的解决方案是使用自平衡的二叉搜索树，例如AVL 树、splay 树或红黑树。它允许您在 O(log n) 时间内通过键访问元素，并以 O(log n + k) 的顺序遍历对象，其中 k 是迭代的元素数。