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

问题描述

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

我明白我需要两个单独的数据结构，我想到有1个和1个优先级队列都按其他参数排序，拿着同一个指针的副本。我遇到的问题是，当我试图从set结构中删除时，我在其他数据结构（Priority Queue）上留下垃圾。

解决方案

哈希表将支持插入，删除和搜索比O（log（n））好得多。这是假设，当您增长桌面时，您不必重新排列所有内容。困难的部分将是在O（1）时间内定位下一个车辆。

根据实现情况， min heap 将在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屋！