在优先级队列中随机访问

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

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

根据您要执行的操作,您可以使用许多其他方法.如果你总是希望访问队列中的第三个元素(而不是任何其他任意位置),那么它可能足够快,只需将两个元素出列,缓存它们,然后将所需的值出列,然后将其他两个元素放回去.

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

如果您需要对排序序列进行真正的随机访问,请考虑使用订单统计树.这是一个扩充的二叉搜索树,支持按索引对元素进行O(log n)访问.您可以使用它来构建优先级队列 - 最小元素始终位于索引0. catch(当然有一个catch)是很难找到一个好的实现和隐藏在O中的常量因子(log n) )术语远高于标准二进制堆.