hello 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 vehicals sorted by their ID and every vehical got a field which represents the time until the next care. i need to extract the vehical that needed to be cared next in O(1) all suggestions are welcome Edited: i understood that i need two seperate 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)
hmmm i know it should envolve a heap but i wont be able to delete or update inside the heap in O(log(n)) the search inside a heap is O(n)
Nadav Stern
2010-09-13 18:20:05
+2
A:
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.
Jim Mischel
2010-09-13 18:36:56
first of all thanks for your answer i understood that i need two seperate 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)
Nadav Stern
2010-09-13 18:43:31
Were I to implement the combined data structure, I'd create the priority queue implementation and ensure that I can delete an arbitrary node. Then, add the hash table functionality that stores nodes, indexed by key. Whenever you want to delete something by key, look it up in the hash table, get the node pointer, and delete it from the priority queue, THEN delete it from the hash table.
Jim Mischel
2010-09-13 18:57:15
how would u implement it so you would be able to delete in O(log(n)) inside the Priority Queue while having the pointer to the needed to be removed data
Nadav Stern
2010-09-13 19:27:25
Deleting from the priority queue is O(log(n)), provided you already know where the node is in the queue. That's why you store priority queue nodes inside the hash table. This works if each priority queue node contains a parent pointer. You look the node up in the hash table (which is an O(1) operation). You now have a reference to the node in the queue, so you can delete it in O(log(n)).
Jim Mischel
2010-09-13 20:01:24