quote:Original post by marijnh
Could you elaborate on those other priority queue implementations? Or give a link or something... i'm wanna know about them!
Here's a one that I tailored for A*. The priority values can only be integers on a specific range (0 - x, where x is feeded on constructor) and with the default template parameters it's not quaranteed to return the absolutely lowest key. It has O(1) push and O(1) pop (IIRC, std:: priority_queue has O(log N) both). But as you can see, the push requires you to feed it with a priority value. std:: priority_queue only requires the elements to be comparable with each other.
It doesn't yet have very interesting constructors, I'll add those later.
template <typename T, class PriorityContainer = std::stack<T>, class BucketContainer = std::vector<PriorityContainer> >class bucket_pqueue {public: typedef PriorityContainer priority_container_type; typedef BucketContainer bucket_container_type; typedef typename priority_container_type::value_type value_type; typedef typename priority_container_type::size_type priority_type; typedef size_t size_type; explicit bucket_pqueue(int buckets) : m_buckets(buckets), m_elements(0), m_minBucket(buckets) {} bool empty() const { return m_elements == 0; } size_type size() const { return m_elements; } void push(const value_type& value, priority_type priority) { m_buckets[priority].push(value); if (priority < m_minBucket) m_minBucket = priority; m_elements++; } const value_type& top() const { return m_buckets[m_minBucket].top(); } value_type& top() { return m_buckets[m_minBucket].top(); } void pop() { m_buckets[m_minBucket].pop(); m_elements--; if (m_elements == 0) { m_minBucket = m_buckets.size(); } else { while (m_buckets[m_minBucket].empty()) m_minBucket++; } } void clear() { while (!empty()) pop(); } private: bucket_container_type m_buckets; size_type m_elements; priority_type m_minBucket;}; Usage:
bucket_pqueue<double> stuff(100); //100 is max prioritystuff.push(3.7, 3); //second parameter is prioritystuff.push(7.3, 10);stuff.push(5.6, 6);assert(stuff.top() == 3.7); //priority was 3stuff.pop();assert(stuff.top() == 5.6); //priority was 6stuff.pop();assert(stuff.top() == 7.3); //priority was 10stuff.pop();assert(stuff.empty()); Very similar to std:: priority_queue, except for the push() and constructor.
Oh, and it's very fast if that's what you want to know
.[edited by - civguy on April 2, 2003 1:12:20 PM]
