I have a need for a priority queue which also tracks the order of insertion of elements, and offers a means to delete the last N inserted items.

I know how I would build that data structure, I'd probably make my own Binary Heap type and have parent offsets in each node, keep them up to date as nodes need to be rearranged over the course of normal Binary Heap operations.

The question is should I? Can you think of any efficient way to do this without making your own data structure?

Efficient means it needs to be better than something equivalent to using "std::BinaryHeap::retain" to scan the entire heap and only retain elements that are deemed to be old enough in "insertion" order.

In case you are wondering what I'm doing with this data structure, I'm building an iterative version of recursive best first search. This can be used for breadth first, uniform cost, or a\* searches depending on how the priority function is defined.

The algorithm I'm implementing is iterative and takes up only O(d \* b) space where d is the depth of the search and b is the branching factor. This is in contrast to the typical priority queue based approach for best first search which stores the entire horizon of the search and can quickly exhaust memory for searches on larger state spaces. The horizon scales as O(b \^ d), which is much much worse. As a tradeoff, the algorithm I'm implementing may revisit nodes its already seen, similar to a depth first search.

As part of this algorithm, I need a priority queue that lets me remove the last N inserted items, for any N. I'm struggling to think of a way of doing it efficiently without making my own custom data structure.

Also I know it sounds like I might be misusing / misunderstanding the purpose of a priority queue given that I need to delete some number of elements that were recently inserted, but that is not the case. I understand what I'm asking for is functionality that doesn't come with most priority queues, and that I either need to make my own data structure or build what I want out of existing data structures.