2

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).

Brian Tompsett - 汤莱恩
  • 5,753
  • 72
  • 57
  • 129
Nadav
  • 2,589
  • 9
  • 44
  • 63
  • 1
    is this homework-related by any chance? – Steve Townsend Sep 13 '10 at 18:15
  • How do you determine which vehicle is next to be cared for? – Nick Larsen Sep 13 '10 at 18:22
  • by his kilometer field ... by kilometers left until next care for example lets say there is a car that got 2k kilometers when it reaches to 0 it needs to be cared – Nadav Sep 13 '10 at 18:24
  • 2
    If this is homework, did you (a) miss the lecture/assigned chapters, (b) not understand the lecture/assigned chapters, (c) are expected to research this in some book or other, (d) expected to research this by asking on the internet or older students who know the answer from last year, (e) expected to invent such a structure for yourself? I rate (d) and (e) as unlikely, but you never know with some teachers. If it's (c) or (e), then answering would be harmful to your education ;-p – Steve Jessop Sep 13 '10 at 18:27
  • Fair enough, then. I hope all your classmates have the decency to upvote the question :-) – Steve Jessop Sep 13 '10 at 21:42

1 Answers1

3

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
  • 131,090
  • 20
  • 188
  • 351
  • 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 Sep 13 '10 at 18:43
  • 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 Sep 13 '10 at 18:57
  • 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 Sep 13 '10 at 19:27
  • 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 Sep 13 '10 at 20:01