Re: [ANN] new module binaryheap 0.1 released

[Coda Highland <chighland@...>]

On Tue, Apr 21, 2015 at 1:38 PM, Oliver Kroth <oliver.kroth@nec-i.de> 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".

http://en.wikipedia.org/wiki/Threaded_binary_tree

/s/ Adam