Re: [ANN] new module binaryheap 0.1 released

[Oliver Kroth <oliver.kroth@...>]

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