Feature request: Priority queue

Discussions Feature Request
#1

Hi is there priority queue in Urho3D?

I’m making a request to have this feature.

User case

For example: if I want to push a struct or object items with a variable of interest (e.g. double time value). What we need is to read the minimum time items and pop the minimum time object from the queue efficiently.

#2

Code like this could benefit (edit from a minheap)

HashMap<String, Timer> changes_;

bool FileWatcher::GetNextChange(String& dest) {
    unsigned delayMsec = (unsigned)(delay_ * 1000.0f);
    if (changes_.Empty())
        return false;
    else {
        for (HashMap<String, Timer>::Iterator i = changes_.Begin(); i != changes_.End(); ++i) {
            if (i->second_.GetMSec(false) >= delayMsec) {
                dest = i->first_;
                changes_.Erase(i);
                return true;
            }
        }
        return false;
    }
}

This article has some performance measurements:

#3

Hi do you think this is faster compares to the insertion sort and pop end item method?

#4

That article draws a conclusion for its own cases one can consider (finding that for more than 64 ints, binary search was faster). If it is that time-critical, maybe it should be tested for one’s specific use case… I would only be speculating, but others may have a better idea.

edit:
Using std, it’s as simple as
priority_queue<int, std::vector<int>, std::greater<int>>
Urho version would take more work; maybe a starting point
https://codeconnect.wordpress.com/2013/09/05/max-min-heap-using-c-stl/

#5

Hi, you can use std::priority_queue to achieve it.

#6

Hi Guys,
Thanks for the comments.
I know about the std priority queue. But my code currently using Urho Vector, So I can use them in Lua script without making any change or adding effort to this feature.

#7

The kNet library that Urho uses has a MaxHeap class - would that work?

#8

Thanks,
I think it would be also good to also have the MinHeap.
I think Urho3D events feature would be more benefit if there is also a min heap.

For example a server based event framework game will execute all earlier events (e.g. distributed events in order to the clients.). This behaviour may be more efficient than sorting of list of events.

Best

1 Like