Datastructures module¶

datastructures.LOWER = 4¶

Module implementing various data structures

class datastructures.Treap(compare=<function <lambda> at 0x7fbd33e4e0c8>, max_size=1000)¶

An implementation of a treap. Note that lower priority elements are at the top. Loosely based on the description in “Randomized Algorithms” by Motwani and Raghavan. All mistakes are mine

Methods

join(T2)¶

Returns the join of self and T2, destroys the heap property of both in the proccess. It assumes T1<=T2

max_tree(node)¶

Returns the maximum value at the tree hanging from node as a root

min_tree(node)¶

Returns the minimum value at the tree hanging from node as a root

move_node_to_root(node)¶

Moves the node to the root, but breaks the heap property in the proccess. Afterwards a splitting a this vertex is trivial

paste(node, T2)¶

Returns a new treap conaining self, the node and the treap T2. The original treaps, self and T2 no longer satisfy the heap property.

predecessor(node)¶

Returns the predecessor of a node

restore_heap(node)¶

Restores the heap property by rotating the node upwards if necessary

restore_heap_downwards(node)¶

Restores the heap property by rotating the node downwards if necessary.

split(key)¶

Splits the treap at the given key value. Note that the old treap no longer satisfies the heap property; should be destroyed but it is difficult and undesirable to do so in Python.

split_at_node(node)¶

Splits the treap a the given node.

successor(node)¶

Returns the succesor of node