When the PQ is full it would be useful to add a new item and have it throw away the lowest priority item

[dizzy2003]

When the PQ is full it would be useful to add a new item and have it throw away the lowest priority item

This feature is useful in a* to have an open set of fixed size, while maintaining just the best N nodes.

The throwing away of the least priority item is the default behaviour I usually see in PQ implementations.

I admit I have only looked at the Fast PQ

[BlueRaja]

Interesting! I haven't heard of this technique before.

If we simply throw the node out, the correctness of A* will be affected (that node could be a part of the best path). How does this technique deal with that?

[dizzy2003]

A* is all ready an approximation to the shortest path assuming the whole tree isnt searched.

The PQ represents the outer edge of the current search area, most searches wont fill it up and will be fine, some searches might fill it up but because the worst nodes are lost they are unlikely to cause an issue with a big enough PQ.

A worst case search though can generate a huge PQ data set, so you either 1. Make the PQ massive, 2 Make the PQ resilient to overflow or 3 have searches throw exceptions and fail.

Option 2 makes best sense to me. It also reduces the time used on worst cases where say a navigation is impossible.

Its also a useful feature when you need N largest items in order from a massive data set.

[BlueRaja]

A* is [already] an approximation to the shortest path

That's false. A guarantees that the shortest path is found, assuming the heuristic used is admissible. A uses a heuristic, but it is not a heuristic itself.

Its also a useful feature when you need N largest items in order from a massive data set

That's also unnecessary. You can solve it in O(k log n) by adding the first n items to the priority queue, then going through the rest of the set, and when an item is larger than queue.First, dequeue the old value and enqueue the new value.

In addition to the above, I'm not entirely sure how you'd even implement this in the queue. I suspect you'd end up having to store a second heap, ordered by max-value instead of min-value.

Given all this, I think I'm going to close this as "won't implement." If necessary, you can achieve this functionality with a second queue.