[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: [ANN] new module binaryheap 0.1 released
- From: Oliver Kroth <oliver.kroth@...>
- Date: Tue, 21 Apr 2015 22:38:45 +0200
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
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.)
Am 21.04.2015 um 21:40 schrieb Thijs Schreijer:
Tests are now complete, and rock has been uploaded
Installing: luarocks install binaryheap
Thx to Boris Nagaev for some fixes
And... another bugfix by Boris, so 0.2 is available through LuaRocks as well now...