结构类似于优先级队列，但具有类似下限的结构

Question

我想要一个结构来存储（例如）数字，我可以在其中插入和删除元素，我的结构始终保持排序（如优先级队列）但有可能知道给定数字在哪里，以及每个操作在对数时间。

也许使用 lower_bound、upper_bound，或者只是二分搜索，但在 priority_queue 中，阻止我进行二分搜索的是我无法访问具有索引的元素，只有第一个。

Answer 1

优先队列不会让事物按顺序排列。至少，通常不会。优先队列使您可以快速获取序列中的下一项。但是您无法有效地访问队列中的第 5 个项目。

我知道三种不同的方法来构建优先级队列，您可以在其中有效地按键访问项目：

使用平衡二叉搜索树实现队列。尽管所有操作都是 O(log n)，但典型的运行时间比二进制堆慢。
将堆优先级队列实现为 skip list。这是一个不错的选择。我看到有人报告说跳跃列表优先级队列优于二进制堆。搜索 [C++ 跳跃列表] 会 return 你有很多实现。
我所说的索引二进制堆也可以。基本上，您将哈希映射或字典与二进制堆结合在一起。 map是通过key来索引的，它的value包含了item在堆数组中的索引。这样的东西不难搭建，而且效果还不错。
想一想，您可以为任何类型的堆创建索引版本。

您有多种选择。我本人更喜欢跳过列表，但您的里程可能会有所不同。

正如我所指出的，索引二叉堆是一种混合数据结构，它维护了一个字典（哈希映射）和一个二叉堆。简要介绍它是如何工作的：

字典键是您用来查找放入堆中的项目的字段。该值是一个整数：该项目在堆中的索引。

堆本身是在数组中实现的标准二进制堆。唯一的区别是，每次将项从堆中的一个位置移动到另一个位置时，都会更新它在字典中的位置。因此，例如，如果你交换两个项目，你不仅要交换数组中的项目本身，还要交换它们在字典中的位置。例如：

heap is an array of string references
dict is a dictionary, keyed by string

swap (a, b)
{
    // swap item at heap[a] with item at heap[b]
    temp = heap[a]
    heap[a] = heap[b]
    heap[b] = temp
    // update their positions in the dictionary
    dict[heap[a]] = b
    dict[heap[b]] = a
}

这是对标准二进制堆实现的一个非常简单的修改。每次移动项目时，您只需要小心更新位置。

您也可以使用基于节点的堆来执行此操作，例如配对堆、斐波那契堆、倾斜堆等。

Answer 2

我认为您正在寻找一个 order statistics tree，一个支持时间 O(log n) 中所有常规 BST 操作的增强 BST，以及其他两个：

rank(elem): return 哪个索引元素将在排序序列中占据。
index(k)：给定索引 k，return 排序序列中该索引处的元素。

以上两个操作运行在O(log n)时间内完成，速度极快。

您可以将订单统计树视为优先级队列。插入像正常的 BST 插入一样工作，要提取 lowest/highest 元素，您只需从树中删除 smallest/greatest 元素，您可以通过向左或向右走在时间 O(log n) 内完成树的刺。

结构类似于优先级队列，但具有类似下限的结构

Structure like priority queue but with something like lower bound

c++

priority-queue

lower-bound

c++11