问如何创建具有运行时间限制的数据结构

EN

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

根据实现的不同，对数将在O(1)和O( min heap (N))(分期)之间插入，找到最小项的时间为O(1)。从堆中删除一项是O(log(n))操作，但在堆中查找任意项的操作多于O(log(n))。

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

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