Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #12622 > unrolled thread
| Started by | samuelmarks@gmail.com |
|---|---|
| First post | 2011-12-17 09:50 -0800 |
| Last post | 2011-12-24 14:24 -0800 |
| Articles | 4 — 3 participants |
Back to article view | Back to comp.lang.c++
O(1) replacement for std::priority_queue samuelmarks@gmail.com - 2011-12-17 09:50 -0800
Re: O(1) replacement for std::priority_queue Michael DOUBEZ <michael.doubez@free.fr> - 2011-12-23 04:11 -0800
Re: O(1) replacement for std::priority_queue Juha Nieminen <nospam@thanks.invalid> - 2011-12-23 16:39 +0000
Re: O(1) replacement for std::priority_queue Michael DOUBEZ <michael.doubez@free.fr> - 2011-12-24 14:24 -0800
| From | samuelmarks@gmail.com |
|---|---|
| Date | 2011-12-17 09:50 -0800 |
| Subject | O(1) replacement for std::priority_queue |
| Message-ID | <24851985.51.1324144205574.JavaMail.geo-discussion-forums@pril5> |
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?
[toc] | [next] | [standalone]
| From | Michael DOUBEZ <michael.doubez@free.fr> |
|---|---|
| Date | 2011-12-23 04:11 -0800 |
| Message-ID | <a9b85496-3923-42ee-8feb-89296a7ee874@f1g2000yqi.googlegroups.com> |
| In reply to | #12622 |
On 17 déc, 18:50, samuelma...@gmail.com 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
[toc] | [prev] | [next] | [standalone]
| From | Juha Nieminen <nospam@thanks.invalid> |
|---|---|
| Date | 2011-12-23 16:39 +0000 |
| Message-ID | <4ef4aec0$0$4370$7b1e8fa0@news.nbl.fi> |
| In reply to | #12758 |
Michael DOUBEZ <michael.doubez@free.fr> 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).
[toc] | [prev] | [next] | [standalone]
| From | Michael DOUBEZ <michael.doubez@free.fr> |
|---|---|
| Date | 2011-12-24 14:24 -0800 |
| Message-ID | <502b32c5-eeb5-4e69-8f04-dd56006559be@g41g2000yqa.googlegroups.com> |
| In reply to | #12773 |
On Dec 23, 5:39 pm, Juha Nieminen <nos...@thanks.invalid> wrote: > Michael DOUBEZ <michael.dou...@free.fr> 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.
[toc] | [prev] | [standalone]
Back to top | Article view | comp.lang.c++
csiph-web