O(1) replacement for std::priority_queue

[samuelmarks]

Can the O(1) Ladder Priority queue (http://dl.acm.org/citation.cfm?id=1103324) be applied generally; e.g. wherever a std:riority_queue is used?

 

[Michael DOUBEZ]

Can the O(1) Ladder Priority queue (http://dl.acm.org/citation.cfm?id=1103324) be applied generally; e.g. wherever a std:riority_queue is used?

Please quote the whole specs, it is not O(1) complexity but "O(1)
average time complexity" ("[...]theoretically justified to be true in
this article on the assumption that the mean of μ is finite and
greater than zero, regardless of its variance.[...]")

Please note that std:riority_queue is intended as a container
adaptor: it inserts the elements in a ordered fashion.

The only point that could be made is that the standard library could
provide a tree-based priority queue (with a min-heap by example).

Michael

 

[Juha Nieminen]

The only point that could be made is that the standard library could
provide a tree-based priority queue (with a min-heap by example).

I thought std:riority_queue already uses a "tree-based" algorithm.
In other words, it organizes the elements as a heap in the vector
(or whatever container is specified).

 

[Michael DOUBEZ]

  I thought std:riority_queue already uses a "tree-based" algorithm.
In other words, it organizes the elements as a heap in the vector
(or whatever container is specified).

So it does. My mistake.