4

I have implemented a PriorityQueue (Max heap) using Java API. Sometimes I need to remove an certain element from the queue, but the method remove() takes O(n) time, is there any way I can improve that to for example O(logn) using this API? Or do I need to implement my own PQ by scratch?

I've tried using a HashMap to store the index of each element, but I have no idea of how to remove an element from the PQ based by the index, is this possible?

I guess in that case the idea would be to:

  • Find the element by index
  • Shift it up in O(logn) time
  • Extract the element in constant time

Any ideas?

Community
  • 1
  • 1
novalain
  • 2,181
  • 19
  • 36
  • I haven't looked the API,but if I wanted a queue with fast removal I would use array based queues. – hermit Aug 25 '15 at 03:42
  • You should instead call PriorityQueue.poll(), which will have O(log(n)) time according to [Java API](http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html) – Charles Spencer Aug 25 '15 at 03:50
  • @hermit you mean a circular array? I think that us even more inefficient than a priority queue. – novalain Aug 25 '15 at 03:55
  • @CharlesSpencer PriorityQueue.poll() only removes the head, I need to remove elements based on some attribute or index.. – novalain Aug 25 '15 at 03:55
  • I don't think this is a duplicate, the other question doesn't relate to the Java API at all. And the link to the implementation in C# does not work. – novalain Aug 25 '15 at 03:57
  • 1
    A PQ isn't intended to support removal of arbitrary elements. Neither is a queue, for that matter. – user207421 Aug 25 '15 at 05:09

0 Answers0