[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: [ANN] new module binaryheap 0.1 released
- From: Coda Highland <chighland@...>
- Date: Tue, 21 Apr 2015 14:04:09 -0700
On Tue, Apr 21, 2015 at 1:38 PM, Oliver Kroth <firstname.lastname@example.org> 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
> 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
Your "treap" is probably more accurately referred to as a "threaded