Search algorithm (with a sort algorithm already implemented)

Im doing a Java application and Im facing some doubts in which concerns performance.

I have a PriorityQueue which guarantees me the element removed is the one with greater priority. That PriorityQueue has instances of class Event (which implements Comparable interface). Each Event is associated with a Entity.

The size of that priorityqueue could be huge and very frequently I will 开发者_如何学JAVAhave to remove events associated to an entity.

Right now Im using an iterator to run all the priorityqueue. However Im finding it heavy and I wonder if there are better alternatives to search and remove events associated with an entity "xpto".

Any suggestions?

Thanks!

---

Theres a few options:

1. Could you use separate queues for each entity? So when you get an event for "xpto" you put it into the XptoPriorityQueue? This will reduce the size of each queue, but could also lead to some other management issues.
2. Are you removing events for a specific entity to process them sooner? If so then you should simply give those entities a higher priority and bump them to the top of the queue.
3. Are you removing events for a specific entity to remove them from the queue and ignore them? If so then they should either never get into the queue or should get a lower priority.

---

A couple of ideas:

1. Implement your priority queue using a treap ordered by the entity's key. If the keys are randomly distributed then you should be able to remove elements in O(log n) time.
2. Maintain a separate mapping of Entity to Events currently in the queue. Instead of actually removing events from the queue immediately, just flip a bit on the Event object indicating it should be ignored when it reaches the front of the queue.

---

Since remove is a linear time operation, you are getting O(N*N) performance.

If you subclass PriorityQueue and create a new method (named removeIf perhaps) that combines the iterator and remove methods then you could reduce this to O(N log(N)).

---

I'd suggest you make a class composed of a PriorityQueue and a Set, with the following operations:

• To add an element, remove it from the Set and, if it weren't there, add it to the PriorityQueue.
• To remove an element, add it to the Set.
• To unqueue an element, unqueue elements from the PriorityQueue until the unqueued element is not present in the Set. Remove any unqueued elements from the Set.

---

It sounds like you need to implement a souped-up priority queue. In particular, you need O(logN) removal time. You can do this by keeping two data structures, an array of Events which is basically the binary heap storing your priority queue, and a HashMap from Event to the offset of that Event in the array (or maybe from Entity to a list of offsets of Events in that array).

You can then do normal heap operations as you would for a priority queue, you just need to update the hash map mappings every time an Event is moved. To remove an Event, look up the index of that event in the hash table and do a remove operation on the heap starting at that index.