Feature request: extract_if method

[vikanezrimaya]

This method should take an FnMut(T) -> bool predicate, and then iterate over items in the priority queue in sorted order, popping and returning those items for which the predicate returns true.

Inspired by Vec::drain_filter(), which is currently marked unstable.

Since it iterates over all elements of the queue, it would obviously be O(n) complexity.

Dropping the iterator object should stop the iteration and preserve the remaining elements of the queue.

An equivalent workaround would be popping all elements of the queue, pushing them back if they don't match the predicate ­— however, I feel like this is prone to being incorrectly implemented (one could accidentally end up in an infinite loop) and/or being inefficient in general (to not end up in a loop, one may push back the unmatched items after the fact — but then collecting those items somewhere, say, in a Vec, is a waste of memory, while creating a second queue to push items back and swapping between queues might not be ergonomic).

[garro95]

It makes sense to me to wait for the std API to be stabilized, to avoid the need for breaking changes in this lib or to have a divergent API with respect to the std.

Some comments on your assumptions though. For the elements to be returned in order, the algorithm needs to be O(n log(n)).
Moreover, being able to iterate in order and to skip elements (i.e. don't remove the elements from the queue) is more challenging than you are prospecting, because of the way the heap algorithm works.

In my opinion, also to be consistent with other iterators (like iter and iter_mut) also the drain_filter implementation should return the elements in arbitrary order.

To have a drain_filter iterator in sorted order, one could convert the priority queue into_sorted_vec, then drain_filter it and finally convert it back into a PriorityQueue.

The complexity of unsorted drain_filter is O(n), while converting the queue into a sorted Vec is O(n log(n)), drain filtering it is O(n) and getting a PriorityQueue back would be O(m log(m)), where m is the number of remaining elements. So the total operation would be O(n log(n)) with one additional allocation for the sorted Vec

[garro95]

drain_filter has been renamed to extract_if now, in Vec