lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

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.)


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...