Rosetta Code Priority Queue

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Rosetta Code Priority Queue

Martin Krpan
I was looking for priority queue and found this implementation on
Rosetta Code (Lua implementation):
https://rosettacode.org/wiki/Priority_queue#Lua

Or I am doing something really stupid or that Lua implementation is not
right. I mean it passes all assertion when i copy/paste and run the
code. But when i change the test code a little it breaks.
If I change n and m parameters in such way that m > n
assertion fails.
Also  if I insert a line
math.randomseed(os.time())
in test then assersion fails too.

I think author is expecting that this line in pop function
            for p, q in pairs(self) do
will return elements sorted by p (and to make things interesting, in
some cases it does).

Anybody care to replace that code for good one?

Martin

Reply | Threaded
Open this post in threaded view
|

Re: Rosetta Code Priority Queue

Luiz Henrique de Figueiredo
Reply | Threaded
Open this post in threaded view
|

Re: Rosetta Code Priority Queue

Nagaev Boris
In reply to this post by Martin Krpan
On Tue, Apr 12, 2016 at 11:12 AM, Martin Krpan <[hidden email]> wrote:

> I was looking for priority queue and found this implementation on
> Rosetta Code (Lua implementation):
> https://rosettacode.org/wiki/Priority_queue#Lua
>
> Or I am doing something really stupid or that Lua implementation is not
> right. I mean it passes all assertion when i copy/paste and run the
> code. But when i change the test code a little it breaks.
> If I change n and m parameters in such way that m > n
> assertion fails.
> Also  if I insert a line
> math.randomseed(os.time())
> in test then assersion fails too.
>
> I think author is expecting that this line in pop function
>             for p, q in pairs(self) do
> will return elements sorted by p (and to make things interesting, in
> some cases it does).
>
> Anybody care to replace that code for good one?
>
> Martin
>

See https://github.com/Tieske/binaryheap.lua

--


Best regards,
Boris Nagaev

Reply | Threaded
Open this post in threaded view
|

Re: Rosetta Code Priority Queue

Matthew Wild
On 12 April 2016 at 13:12, Nagaev Boris <[hidden email]> wrote:
> On Tue, Apr 12, 2016 at 11:12 AM, Martin Krpan <[hidden email]> wrote:
>> I was looking for priority queue and found this implementation on
>> Rosetta Code (Lua implementation):
>> https://rosettacode.org/wiki/Priority_queue#Lua
>
> See https://github.com/Tieske/binaryheap.lua

For the sake of completeness:
https://hg.prosody.im/trunk/file/tip/util/indexedbheap.lua (though
it's not packaged outside of Prosody).

Regards,
Matthew