Boost: Priority Queue which supports finding an element in O(log n) time

Question

I am curious whether Boost offers Priority Queue implementation which also supports finding an element in time O(log n)?

I could achieve this functionality by using a Boost Fibonacci Heap, and store the handles in a std::map together with their index and update this information upon heap insert, but I was hoping for a heap version which already offers this functionality.

Note: I deleted the previous version of my question because it was too ambiguous.

A `multiset` is a priority queue that supports finding stuff in logarithmic time. — tmyklebu, Jun 24 '14 at 22:44
I think it's implicit that key-order or "natural" order doesn't coincide with priority here. @tmyklebu has a point there — sehe, Jun 24 '14 at 22:45
@sehe You can use a `(multi)set >` or `multimap` or if the priority can be calculated easily from the items a `(multi)set` with custom comparator. — Csq, Jun 24 '14 at 22:46
@Csq AFAIK, a map does not support the priority queue operations in adequate time. — user695652, Jun 24 '14 at 22:47
@user695652 the intent of my original comment was to ask what operations are slow for you — Csq, Jun 24 '14 at 22:48
On average, depending on the "load factor" of each priority bucket and also the implementation of the sublists in the multimap, that could work just fine. Profiling would tell you — sehe, Jun 24 '14 at 22:49
@Csq Ah sorry, well the min-key element should be accessible in O(1) time, a new element should be inserted and removed in O(\log n) time — user695652, Jun 24 '14 at 22:51

score 2 · Answer 1 · edited May 23 '17 at 12:20

If you don't mind having (considerable?) overhead in space and insertion time, you can use a multi-index container here.

For an idea, here's an example that employs Boost Multi-Index to do a priority-queue implementing Active Object pattern on top of Boost Asio:

boost::asio and Active Object

It should be noted that Multi-Index let's you specify any number of secondary/auxiliary indices on the same container

Csq · Answer 2 · 2014-06-24T23:02:47.003

You can use

(multi)set<pair<priority, item> >
multimap<priority, item>
(multi)set<item> with custom comparator if the priority can be calculated easily from the items.

to store the elements.

If you need O(1) access for the top element you can use an own container that is backed by a set-like structure described above and stores an iterator to the first element and updates it when needed.

I'm not sure whether this solution performace-wise is better than other approaches but it can be implemented and measured fast. Most operations on sets are O(n*log(n)), just like on a priority queue but in overall the set should be slower as it is scattered in the memory.

Stefan · Answer 3 · 2014-06-25T09:48:07.357

The only way to find an element in a priority queue in less-than-linear time without sacrificing the asymptotic performance of priority queue operations is to keep track of the position of each element upon each priority queue operation.

The only library I found that provides the necessary functionality is libpqueue, now available here: https://github.com/vy/libpqueue.

It works by using user-defined callback functions cmppri(), getpri(), setpri(), getpos(), setpos(), which are called by the library each time the queue is updated.

The intended usage pattern is to define a wrapper data structure like:

typedef struct {
    pqueue_pri_t pri;
    void *data;
    size_t pos;
} node_t;

and accessor functions like:

static size_t get_pos(void *a) {
    return ((node_t *) a)->pos;
}

static void set_pos(void *a, size_t pos) {
    ((node_t *) a)->pos = pos;
}

This allows one to find the position of a node in O(1) time, at the expense of the overhead for creating the wrapper structure and the callback calls. If you need to find an element by name (and not by node_t pointer), you can easily use a std::unordered_map or similar as a backend.

libpqueue is standalone plain C under Apache license.

Boost: Priority Queue which supports finding an element in O(log n) time

3 Answers3