Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > O(1) replacement for std::priority_queue

Reply
Thread Tools

O(1) replacement for std::priority_queue

 
 
samuelmarks@gmail.com
Guest
Posts: n/a
 
      12-17-2011
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?
 
Reply With Quote
 
 
 
 
Michael DOUBEZ
Guest
Posts: n/a
 
      12-23-2011
On 17 déc, 18:50, (E-Mail Removed) wrote:
> 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
 
Reply With Quote
 
 
 
 
Juha Nieminen
Guest
Posts: n/a
 
      12-23-2011
Michael DOUBEZ <(E-Mail Removed)> 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: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).
 
Reply With Quote
 
Michael DOUBEZ
Guest
Posts: n/a
 
      12-24-2011
On Dec 23, 5:39*pm, Juha Nieminen <(E-Mail Removed)> wrote:
> Michael DOUBEZ <(E-Mail Removed)> 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: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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Replacement PSU for an ADSL Router Edward W. Thompson Wireless Networking 0 09-06-2005 10:40 AM
Replacement for FF calendar extension Dan Firefox 5 03-23-2005 08:38 PM
Replacement for AOL newsgroup access EJGroth Firefox 0 02-08-2005 02:41 PM
Calendar replacement William W. Plummer Firefox 1 07-02-2004 04:10 PM
Replacement For Access Point KS Wireless Networking 1 06-24-2004 04:40 AM



Advertisments