如何创建具有运行时限的数据结构 [英] How to create a data structure with run time limits

问题描述

我需要实现一个支持在
O（log（n））中插入删除和搜索并在O（1）中提取特殊对象的数据结构。
我的数据结构需要持有车辆按他们的ID排序，每辆车都有一个字段，代表到下一个服务的时间。
我需要提取在O（1）中需要服务的车辆。
欢迎所有建议。

我知道我需要两个独立的数据结构，我想到有1个和1个优先级队列都被其他参数排序，但是持有相同指针的副本。我有的问题是，当我试图删除从设置结构，我留在垃圾对其他数据结构（优先级队列）。

解决方案

哈希表将支持插入，删除和搜索比O（log（n））更好。这是假设你永远不需要重新哈希一切，当你成长的表。困难的部分是在O（1）时间内找到下一个车辆。

根据实现，最小堆将给你之间的O（1）和O（log（n））（摊销）插入，并找到最小项是O（1）。从堆中删除项是一个O（log（n））操作，但是发现堆中的任意项大于O（log（n））。

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

其实，可能，虽然可能是混乱的，结合两个数据结构，以便您的哈希表存储堆节点对象（其中有对实际数据的引用），而不是实际的数据对象。只要堆节点知道它在堆中的位置（即，具有父指针以及左和右子指针），则可以使用哈希表来查找节点并从堆中删除该节点。 p>

I need to implement a data structure that supports insertion deletion and search in O(log(n)) and extracting a special object in O(1). My Data structure needs to hold vehicles sorted by their ID and every vehicle has a field which represents the time until the next service. I need to extract the vehicles that needed to be services next in O(1). All suggestions are welcome.

I understood that I need two separate data structures and I thought about having 1 set and 1 priority Queue both sorted by other parameters but holding the copy of the same pointer. The problem I have, is that when I am trying to delete from the "set" structure, I stay with garbage on the other data structure (priority Queue).

解决方案

A hash table will support insertion, deletion, and search in much better than O(log(n)). That's assuming that you never have to re-hash everything when you grow the table. The difficult part would be locating the "next" vehicle in O(1) time.

Depending on the implementation, a min heap will give you between O(1) and O(log(n)) (amortized) insertion, and finding the minimum item is O(1). Deleting an item from the heap is an O(log(n)) operation, but finding an arbitrary item in the heap is more than O(log(n)).

Were I to implement this, I'd use two separate data structures: a hash table and a min heap. The reasoning is that the hash table provides very fast insertion, deletion, and lookup, and the heap provides ordering based on service time. The only place where this doesn't meet your started requirements is in deleting a vehicle, because that requires searching the heap for an arbitrary item.

Actually, it'd be possible, although probably messy, to combine the two data structures so that your hash table stores heap node objects (which have a reference to the actual data) rather than the actual data objects. As long as the heap node knows where it is in the heap (i.e. has a parent pointer as well as left and right child pointers), then you can use the hash table to find a node and remove that node from the heap.

这篇关于如何创建具有运行时限的数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！