[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: [ANN] new module binaryheap 0.1 released
- From: Oliver Kroth <oliver.kroth@...>
- Date: Wed, 22 Apr 2015 06:53:08 +0200
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
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