我需要实现一个支持插入删除和搜索的数据结构
O(log(n)) 并在 O(1) 中提取特殊对象。
我的数据结构需要保存按 ID 排序的车辆，并且每辆车都有一个字段表示距离下一次服务的时间。
我需要在 O(1) 时间内提取接下来需要提供服务的车辆。
欢迎所有建议。
我知道我需要两个单独的数据结构，并且我考虑拥有 1 个集合和 1 个优先级队列，两者均按其他参数排序，但保留同一指针的副本。我遇到的问题是，当我尝试从“集合”结构中删除时，我会在其他数据结构（优先级队列）上保留垃圾。
哈希表比 O(log(n)) 更好地支持插入、删除和搜索。这是假设当你增长表时你永远不需要重新散列所有内容。困难的部分是在 O(1) 时间内找到“下一辆车”。
根据实施情况，min heap将为您提供 O(1) 和 O(log(n)) （摊销）之间的插入，并且找到最小项的时间为 O(1)。从堆中删除一个项目是一个 O(log(n)) 操作，但是finding堆中的任意项都超过 O(log(n))。
如果我要实现这个，我将使用两个独立的数据结构：哈希表和最小堆。原因是哈希表提供非常快速的插入、删除和查找，而堆提供基于服务时间的排序。唯一不满足您开始要求的地方是删除车辆，因为这需要在堆中搜索任意项目。
实际上，虽然可能很混乱，但可以组合这两种数据结构，以便哈希表存储堆节点对象（它具有对实际数据的引用）而不是实际的数据对象。只要堆节点知道它在堆中的位置（即具有父指针以及左子指针和右子指针），就可以使用哈希表查找节点并将该节点从堆中删除。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
