Okay, so, I decided to scrap the BinaryHeap version of the
priority queue, going back to basics and utilizing a simple
array. It works, huzzah!
Code:
module data_structures.priority_queue;
import std.array;
import std.range: assumeSorted;
import std.typecons: Tuple;
/*
Templated
On Thursday, 6 August 2015 at 09:08:04 UTC, John Colvin wrote:
Worst case for getting root off a binary heap is O(log(N)),
copying the whole thing is O(N).
Those numbers does not take into account the special properties
of *in-array-packed* implementation of a binary heap. They are
On Thursday, 6 August 2015 at 08:44:17 UTC, Per Nordlöw wrote:
On Wednesday, 5 August 2015 at 18:20:41 UTC, John Colvin wrote:
[...]
I suggest you rehearse on how a binary heap works. A binary
heap with array storage trades speed for memory compactness, a
bit similar to how quick sort
On Wednesday, 5 August 2015 at 18:20:41 UTC, John Colvin wrote:
in my vision, either x.popFront would also create a copy or you
would have to go auto y = x.nonModifyingView or similar. What
I don't want is something that copies 1 elements just to
use x.take(6)
I suggest you rehearse on
On Wednesday, 5 August 2015 at 01:02:56 UTC, DarthCthulhu wrote:
I must be doing something really stupid here, but I have no
clue what it is. Anyone know?
For functional behaviour I prefer a postblit that duplicates the
underlying BinaryHeap.
On Wednesday, 5 August 2015 at 02:26:48 UTC, Meta wrote:
It looks like there was a breaking change made to BinaryHeap
somewhere between 2.065 and the present. The code compiles fine
on 2.065.
http://dpaste.dzfl.pl/65ba735d69e7
It was this PR that changed the behaviour:
On Wednesday, 5 August 2015 at 09:04:54 UTC, Nordlöw wrote:
For functional behaviour I prefer a postblit that duplicates
the underlying BinaryHeap.
The postblit is the
this(this) { ... }
On Wednesday, 5 August 2015 at 09:04:54 UTC, Nordlöw wrote:
This will however duplicate the underlying array aswell, which
is probably not what we want. How do we avoid this?
Correction: the underlying storage array *must* be duplicated
whenever we want to iterate over it without side effects
On 8/5/15 7:09 AM, Per =?UTF-8?B?Tm9yZGzDtnci?=
per.nord...@gmail.com wrote:
On Wednesday, 5 August 2015 at 09:04:54 UTC, Nordlöw wrote:
This will however duplicate the underlying array aswell, which is
probably not what we want. How do we avoid this?
Correction: the underlying storage array
On Wednesday, 5 August 2015 at 11:09:29 UTC, Per Nordlöw wrote:
On Wednesday, 5 August 2015 at 09:04:54 UTC, Nordlöw wrote:
This will however duplicate the underlying array aswell, which
is probably not what we want. How do we avoid this?
Correction: the underlying storage array *must* be
On Wednesday, 5 August 2015 at 13:37:19 UTC, John Colvin wrote:
On Wednesday, 5 August 2015 at 11:09:29 UTC, Per Nordlöw wrote:
On Wednesday, 5 August 2015 at 09:04:54 UTC, Nordlöw wrote:
This will however duplicate the underlying array aswell,
which is probably not what we want. How do we
On Wednesday, 5 August 2015 at 15:29:39 UTC, Nordlöw wrote:
On Wednesday, 5 August 2015 at 13:37:19 UTC, John Colvin wrote:
On Wednesday, 5 August 2015 at 11:09:29 UTC, Per Nordlöw wrote:
On Wednesday, 5 August 2015 at 09:04:54 UTC, Nordlöw wrote:
This will however duplicate the underlying
On Wednesday, 5 August 2015 at 09:04:54 UTC, Nordlöw wrote:
On Wednesday, 5 August 2015 at 01:02:56 UTC, DarthCthulhu wrote:
I must be doing something really stupid here, but I have no
clue what it is. Anyone know?
For functional behaviour I prefer a postblit that duplicates
the underlying
So I've just gotten into D and decided to have a go at creating
something relatively simple to get my feet wet: a priority queue.
Seemed like a simple enough thing, right? It's a pretty basic
data structure, it can't possibly be THAT difficult, right?
First, I tried using associative arrays
On Wednesday, 5 August 2015 at 01:27:53 UTC, Steven Schveighoffer
wrote:
On 8/4/15 9:02 PM, DarthCthulhu wrote:
writefln(PQ: %s, pq.queue); - prints PQ: [Tuple!(int,
string)(3,
HELLO3), Tuple!(int, string)(10, HELLO10), Tuple!(int,
string)(11,
HELLO11)]
This is probably consuming your
On Wednesday, 5 August 2015 at 01:27:53 UTC, Steven Schveighoffer
wrote:
On 8/4/15 9:02 PM, DarthCthulhu wrote:
writefln(PQ: %s, pq.queue); - prints PQ: [Tuple!(int,
string)(3,
HELLO3), Tuple!(int, string)(10, HELLO10), Tuple!(int,
string)(11,
HELLO11)]
This is probably consuming your
On Wednesday, 5 August 2015 at 02:26:48 UTC, Meta wrote:
On Wednesday, 5 August 2015 at 01:27:53 UTC, Steven
Schveighoffer wrote:
On 8/4/15 9:02 PM, DarthCthulhu wrote:
writefln(PQ: %s, pq.queue); - prints PQ: [Tuple!(int,
string)(3,
HELLO3), Tuple!(int, string)(10, HELLO10), Tuple!(int,
On 8/4/15 9:02 PM, DarthCthulhu wrote:
writefln(PQ: %s, pq.queue); - prints PQ: [Tuple!(int, string)(3,
HELLO3), Tuple!(int, string)(10, HELLO10), Tuple!(int, string)(11,
HELLO11)]
This is probably consuming your queue, popping all the data off as it
prints. If you print the length
18 matches
Mail list logo
