O(1) replacement for std::priority_queue

Discussion in 'C++' started by samuelmarks@gmail.com, Dec 17, 2011.

  1. Guest

    , Dec 17, 2011
    #1
    1. Advertising

  2. On 17 déc, 18:50, wrote:
    > Can the O(1) Ladder Priority queue (http://dl.acm.org/citation.cfm?id=1103324) be applied generally; e.g. wherever a std::priority_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::priority_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
    Michael DOUBEZ, Dec 23, 2011
    #2
    1. Advertising

  3. Michael DOUBEZ <> wrote:
    > 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::priority_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).
    Juha Nieminen, Dec 23, 2011
    #3
  4. On Dec 23, 5:39 pm, Juha Nieminen <> wrote:
    > Michael DOUBEZ <> wrote:
    > > 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::priority_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.
    Michael DOUBEZ, Dec 24, 2011
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tino

    clearing a priority_queue

    Tino, Jul 9, 2003, in forum: C++
    Replies:
    4
    Views:
    1,145
    Stuart Golodetz
    Jul 9, 2003
  2. newsock

    queue, deque, priority_queue

    newsock, Oct 24, 2003, in forum: C++
    Replies:
    15
    Views:
    2,406
    Tim Clacy
    Nov 4, 2003
  3. Tino
    Replies:
    3
    Views:
    750
    rossum
    May 28, 2004
  4. red floyd

    std::priority_queue derivable?

    red floyd, Jun 16, 2004, in forum: C++
    Replies:
    2
    Views:
    443
    red floyd
    Jun 16, 2004
  5. Jeremy Murphy
    Replies:
    5
    Views:
    464
    Jeremy Murphy
    Dec 13, 2012
Loading...

Share This Page