Re: [ANN] new module binaryheap 0.1 released

[Coda Highland <chighland@...>]

On Tue, Apr 21, 2015 at 9:53 PM, Oliver Kroth <oliver.kroth@nec-i.de> wrote:
> Coda,
>
> no, that is another structure with additional pointers. In a treap, each
> node has two pointers, but also two values that are sorted independently.
>
> A treap is first a normal binary tree, where all left children have a value
> less than or equal to the node's own value, and all right children have a
> greater or equal value.
> As such, the nbinary tree is sorted left to right for the value.
>
> Additionally, the tree is sorted from root to the leaves as a heap, i.e.
> each node has a higher or same priority than all its children.
>
> After each operation on the binary tree structure, the heap has to be
> reestablished with left-right or right-left-rotations of three adjacent
> nodes until the hep condition is met again. The effort for all operations is
> O(log n), only peeking at the root, the element with the highest priority,
> is O(1).
>
> You may look at Wikipedia: http://en.wikipedia.org/wiki/Treap
>
> --
> Oliver
>
> Am 21.04.2015 um 23:04 schrieb Coda Highland:
>>
>> Your "treap" is probably more accurately referred to as a "threaded binary
>> tree". http://en.wikipedia.org/wiki/Threaded_binary_tree /s/ Adam
>

Learn something new every day. Also I was improperly taught the
definition of threaded binary trees in school, now that I've read the
Wikipedia article more closely.

/s/ Adam