RE: [ANN] new module binaryheap 0.1 released

[Thijs Schreijer <thijs@...>]

> -----Original Message-----
> From: lua-l-bounces@lists.lua.org [mailto:lua-l-bounces@lists.lua.org] On
> Behalf Of Oliver Kroth
> Sent: dinsdag 21 april 2015 22:39
> To: lua-l@lists.lua.org
> Subject: Re: [ANN] new module binaryheap 0.1 released
> 
> Great job, Thijs!
> 
> I like the reverse lookup as it it accelerates finding a given node from
> O(n) to O(1), which is only possible using Lua's hash table functionality.
> 
> Without this, one may use a so called treap, which is a binary heap (as
> we have it already), which additionally is a binary tree sorted on the
> node's values.
> It is a tree for the values, and a heap for the priorities (or times), a
> tree-heap, a "treap".
> As in any binary tree, look-up operation for a given value requires
> effort O(log n).
> However, we would need a traditional tree with pointers (i.e.
> references). And the treap requires to get sorted in both directions
> with each insertion and deletion, which takes more time than sorting for
> only one direction. (It's for both structure O(log n), but the hidden
> factor is larger for the treap.)
> 
> --
> Oliver
> 

I've been thinking of making it more general purpose, and add other structures/algorithms (for self-educational purposes I have a red-black tree on my list to develop). And so make a module that contains multiple of those.

Every once in a while I see questions like this, and some code flying by in the list. So maybe it's worth the effort to collect them, with some documentation and tests.

Thijs