Tail Trim Priority Queue

[splitice]

Sometimes you only want the top N results, in this case it makes sense to implement an a method to remove the lowest priority N results.

Currently the only way to do this is to build a new Queue. i.e

                if (_collection.Count > 1024)
                {
                    var c = new FastPriorityQueue<PrioOccurancePossibility>(2048);
                    foreach(var cc in _collection.Take(1024)) c.Enqueue(cc, cc.Priority);
                    _collection = c;
                }

[BlueRaja]

I'm not sure if there's a more efficient way to do this with a heap priority queue. What is the use-case for this?

[splitice]

Applications that I can think of are search results, machine learning, search space limiting w/ path finding. Basically anywhere you need the top scored results.

Am I missing something. I would think that this wouldnt need anything more than just an Array.Clear on the latter part & to change the value of _numNodes?

[BlueRaja]

It's implemented as an array, but it's not a sorted array. Heaps are not search-trees, they only satisfy the heap property. The front of the queue is always the root node, but there is no way (to my knowledge) to find the end of the queue, aside from scanning all the leaf-nodes (~n/2 = O(n))

[BlueRaja]

I'm going to close this given that I don't know how to implement it more efficiently than creating a new priority queue. If you figure something out, please reopen and comment.