lua-users home
lua-l archive

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

On Tue, Apr 21, 2015 at 1:38 PM, Oliver Kroth <> wrote:
> 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

Your "treap" is probably more accurately referred to as a "threaded
binary tree".

/s/ Adam