c++ - 如何创建具有运行时限制的数据结构

Question

我需要实现一个支持插入删除和查找的数据结构O(log(n)) 并在 O(1) 中提取一个特殊对象。我的数据结构需要保存按 ID 排序的车辆，每辆车都有一个字段代表下一次服务之前的时间。我需要在 O(1) 中提取下一个需要服务的车辆。欢迎提出所有建议。

我知道我需要两个单独的数据结构，我考虑过让 1 个集合和 1 个优先级队列都按其他参数排序但保存同一指针的拷贝。我遇到的问题是，当我试图从“set”结构中删除时，我在另一个数据结构(优先队列)上留下了垃圾。

Answer 1

哈希表将支持插入、删除和搜索，比 O(log(n)) 好得多。这是假设您在扩大表格时永远不必重新散列所有内容。困难的部分是在 O(1) 时间内定位“下一个”车辆。

根据实现，min heap会给你 O(1) 和 O(log(n)) (摊销)插入，找到最小项是 O(1)。从堆中删除一个项目是一个 O(log(n)) 操作，但是找到堆中的任意项目超过 O(log(n))。

如果我要实现这个，我会使用两个独立的数据结构:一个哈希表和一个最小堆。原因是哈希表提供了非常快速的插入、删除和查找，而堆提供了基于服务时间的排序。唯一不符合您开始要求的地方是删除车辆，因为这需要在堆中搜索任意项目。

实际上，尽管可能会很困惑，但可以将这两种数据结构组合起来，以便您的哈希表存储堆节点对象(具有对实际数据的引用)而不是实际数据对象。只要堆节点知道它在堆中的位置(即有一个父指针以及左右子指针)，那么您就可以使用哈希表找到一个节点并将该节点从堆中删除。