c++ - 在优先队列中随机访问

Question

如何在优先级队列中随机访问/搜索？。例如，如果有一个像 q={5,4,3,2,1} 这样的优先级队列，例如，我想直接访问第 3 个值，即 3，我不能这样做，是否有任何进程可以随机访问优先队列？

Answer 1

大多数优先级队列实现，包括 C++ std::priority_queue 类型，不支持随机访问。优先队列背后的想法是牺牲随机访问来快速访问最小的元素。

根据您要执行的操作，您可以使用许多其他方法。如果您总是想要访问队列中的第三个元素(而不是任何其他任意位置)，它可能足够快，只需出列两个元素，缓存它们，然后出列您想要的值并将其他两个元素返回。

如果您想在任何时间点访问第 k 个最小的元素，其中 k 较大，一种选择是存储两个不同的优先级队列:一个包含 k 个元素的反向排序优先级队列(称为左队列) 和一个包含剩余 n-k 个元素的常规优先级队列(称为右队列)。要获得第 k 个最小的元素，从左队列中出队(返回第 k 个最小的元素)，然后从右侧出队一个元素并入队到左侧以将其返回到总共 k 个元素。要进行入队，请检查数字是否小于左侧队列的顶部。如果是，则从左队列中出队，将移除的元素入队到右队列中，然后将原始元素入队到左队列中。否则，向右排队。这保证了每个操作的 O(log n) 运行时间。

如果您需要对排序序列进行真正的随机访问，请考虑使用顺序统计树。这是一个增强的二叉搜索树，支持通过索引对元素进行 O(log n) 访问。您可以使用它来构建一个优先级队列 - 最小元素始终位于索引 0 处。问题(当然有一个问题)是很难找到一个好的实现和隐藏在 O(log n ) 项比标准二进制堆中的项高得多。