 |
lua-l archive |
|
|
||
|
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 Am 21.04.2015 um 21:40 schrieb Thijs Schreijer:
Tests are now complete, and rock has been uploaded Code: https://github.com/Tieske/binaryheap.lua Docs: http://tieske.github.io/binaryheap.lua/ Installing: luarocks install binaryheap Thx to Boris Nagaev for some fixes ThijsAnd... another bugfix by Boris, so 0.2 is available through LuaRocks as well now... Thijs