我需要实现一个支持插入删除的数据结构和 O（日志（n））的搜索的O提取的特殊对象（1）。 我的数据结构需要保存按其ID排序的车辆，并且每辆车都有一个表示直到下一次维修的时间的字段。 我需要在O（1）中提取需要服务的车辆。 欢迎您提出任何建议。如何创建与运行时间限制的数据结构
予理解的是，我需要两个单独的数据结构和I想到具有1组和1个优先级队列都由其他参数排序但保持相同的指针的副本。我遇到的问题是，当我试图从“set”结构中删除时，我在其他数据结构（优先级队列）上留下垃圾。
哈希表将支持插入，删除，和更好的搜索比O（日志（N））。这是假设你在增长表格时从不需要重新散列所有内容。困难的部分是在O（1）时间定位“下一个”车辆。
根据具体实施情况，min heap会在O（1）和O（log（n））（摊销）之间插入，并且找到最小项目为O（1）。从堆中删除项是O（log（n））操作，但找到堆中的任意项大于O（log（n））。
是我实现这一点，我会使用两个单独的数据结构：哈希表和最小堆。理由是哈希表提供非常快的插入，删除和查找，并且堆提供基于服务时间的排序。唯一不符合您的起始要求的地方是删除车辆，因为这需要在堆中搜索任意物品。
事实上，虽然可能很麻烦，但将两个数据结构合并在一起，以便您的哈希表存储堆节点对象（对实际数据有引用）而非实际数据对象。只要堆节点知道它在堆中的位置（即具有父指针以及左和右子指针），那么可以使用散列表来查找节点并从堆中移除该节点。
首先感谢您的回答 我了解，我需要两个不同的数据结构，我想大约有1套和1个优先级队列都被其他参数进行排序，但持有相同指针的副本。我遇到的问题是，当我试图从“set”结构中删除我留在其他数据结构（优先级队列）上的垃圾时 – 2010-09-13 18:43:31
如果我要实现组合数据结构，我会创建优先级队列实现并确保我可以删除任意节点。然后，添加存储节点的散列表功能，按键索引。无论何时您想通过键删除某些内容，请在散列表中查找它，获取节点指针，然后将其从优先级队列中删除，然后将其从哈希表中删除。 – 2010-09-13 18:57:15
你将如何实现它，这样你就可以在优先级队列中删除O（log（n）），同时指向需要删除的数据 – 2010-09-13 19:27:25
是否有这个作业相关的任何机会？ – 2010-09-13 18:15:19
家庭作业看起来很可能 – 2010-09-13 18:16:07
你如何确定下一辆车是否需要照顾？ – 2010-09-13 18:22:56