PriorityQueue removing an element

[Mark Proctor]

Is there a way to remove a specific element from a queue? I can only see that it's possible to dequeue(), but no actual remove(element) ?

Mark

[Sebastiano Vigna]

That's not part of the methods of a queue (as an abstract data type) Probably you need a sorted set instead.

[Mark Proctor]

Oracle has added remove(Object o).  Although I suspect this remove() operation, would be too slow a search.

https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

We need to avoid doing an unnecessary full sort, not everything that is queued will be executed. A binary heap is a standard data structure for a production rule system, to ensure you fire the most prioritised rule, without wasting cpu on a full. Many rules will be cancelled before they fire, due to underlying changes in data.

Ages ago we wrote this, where the interface of the queued item  supports fast removal:

https://github.com/mdproctor/drools/blob/main/drools-core/src/main/java/org/drools/core/util/BinaryHeapQueue.java

See line 316 setElement, which is called during perculateUp and perculateDown, by recording the index we are able to do a fast removal by dequeuing a specific index, see line 186.

Would you be interested in a PR, that adds an optional similar interface and fast removal behaviour to your array based heap queues? We are trying to remove all of our custom collections. The cost would be a single boolean statement, configured at constructor time, as well as the addition of the optional interface that must be implemented by the enqueued/dequeued item?

Regards

Mark

[Mark Proctor]

Having a quick scan of the code.  

This would obviously only work for ObjectHeapPriorityQueue, so it could not go on the PriorityQueue interface - but would be a specialisation of the concrete class. If you are open to a PR like this, please let me know.

It would be possible to do something with primitives, via user callbacks as int positions are changes - but not sure it's worth the complexity.

Mark

[Sebastiano Vigna]

> On 26 Jan 2023, at 13:38, Mark Proctor <mdpr...@gmail.com> wrote:
>
> Oracle has added remove(Object o). Although I suspect this remove() operation, would be too slow a search.
> https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

Oracle doesn't get to define what queue is 😂.

> See line 316 setElement, which is called during perculateUp and perculateDown, by recording the index we are able to do a fast removal by dequeuing a specific index, see line 186.

I think you need an indirect queue. That's what you use when you need removal. How are you going to get the position of an element othewise?

https://fastutil.di.unimi.it/docs/it/unimi/dsi/fastutil/IndirectPriorityQueue.html

Ciao,

seba

[Mark Proctor]

On Friday, 27 January 2023 at 08:16:05 UTC Sebastiano Vigna wrote:

> On 26 Jan 2023, at 13:38, Mark Proctor <mdpr> wrote:
>
> Oracle has added remove(Object o). Although I suspect this remove() operation, would be too slow a search.
> https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

Oracle doesn't get to define what queue is 😂.

> See line 316 setElement, which is called during perculateUp and perculateDown, by recording the index we are able to do a fast removal by dequeuing a specific index, see line 186.

I think you need an indirect queue. That's what you use when you need removal. How are you going to get the position of an element othewise?

https://fastutil.di.unimi.it/docs/it/unimi/dsi/fastutil/IndirectPriorityQueue.html

I looked at indirect queue, and in theory it does this, but it requires a fixed size array. A production rule system might produce a 10 or it might produce a million items on the queue. I'd also need to track the empty indexes on a stack (after an entry is dequeued), so they can be  re-used. As mentioned the work around in my implementation was to simply allow the queued item to store its index position, via an interface. I'll do a PR anyway, shouldn't take to long, will be easier to discuss it from there.

 

Ciao,

seba

[Sebastiano Vigna]

> On 27 Jan 2023, at 14:30, Mark Proctor <mdpr...@gmail.com> wrote:
>
>
> https://fastutil.di.unimi.it/docs/it/unimi/dsi/fastutil/IndirectPriorityQueue.html
> I looked at indirect queue, and in theory it does this, but it requires a fixed size array. A production rule system might produce a 10 or it might produce a million items on the queue. I'd also need to track the empty indexes on a stack (after an entry is dequeued), so they can be re-used. As mentioned the work around in my implementation was to simply allow the queued item to store its index position, via an interface. I'll do a PR anyway, shouldn't take to long, will be easier to discuss it from there.

I don't understand--and what do you do when you move elements around--you change their index?

Ciao,

seba