Python Treap implementation [on hold]

I know there are probably many problems with this (since I haven't tested it yet), but I'd appreciate any advice (stylistic hints as well).

from functools import total_ordering import random  def treapnode(key,priority,prnt,lchild,rchild):     return {'key':key,'priority':priority,'prnt':prnt,'lchild':lchild,'rchild':rchild}  # greater than any priority (never lt) @total_ordering class End(object):     def __lt__(self,other):         return 0  def rotateleft(root,rchild):      root['rchild'] = rchild['lchild']     rchild['lchild'] = root      #fix parent relationships     if root == root['prnt']['lchild']:         root['prnt']['lchild'] = rchild     else:         root['prnt']['rchild'] = rchild      rchild['prnt'] = root['prnt']     root['prnt'] = rchild     root['rchild']['prnt'] = root  def rotateright(root,lchild):     root['lchild'] = lchild['rchild']     lchild['rchild'] = root      if root == root['prnt']['lchild']:         root['prnt']['lchild'] = lchild     else:         root['prnt']['rchild'] = lchild      lchild['prnt'] = root['prnt']     root['lchild']['prnt'] = root     root['prnt'] = lchild      def bubble_down(node):     while node['lchild'] or node['rchild']:         if node['lchild'] and node['rchild'] and node['rchild']['priority'] < node['lchild']['priority']:             if node['rchild']['priority'] < node['priority']:                 rotateleft(node, node['rchild'])         if node['lchild'] and node['lchild']['priority'] < node['priority']:             rotateright(node,node['lchild'])         else:             break  def bubble_up(node):     while node['prnt']:         if node['priority'] < node['prnt']['priority']:             if node == node['prnt']['rchild']:                 rotateleft(node['prnt'], node)             else:                 rotateright(node['prnt'],node)         else:             break  def insert(root,key):     # invariant: root != None     while root['rchild'] or root['lchild']:         if root['key'] <= key and root['rchild']:             root = root['rchild']         elif root['key'] > key and root['lchild']:             root = root['lchild']         else:             break      newnode = treapnode(key, random.uniform(0,1), None, None,None)     if root['key'] <= key:         root['rchild'] = newnode     else:         root['lchild'] = newnode      return newnode  def delete(node):     def reassignprnt(nodeschild):         if node == node['prnt']['lchild']:             node['prnt']['lchild'] = nodeschild         else:             node['prnt']['rchild'] = nodeschild      if node['lchild'] or node['rchild']:         if not node['lchild']:             reassignprnt(node['rchild'])         elif not node['rchild']:             reassignprnt(node['lchild'])         else:             node['value'] = End()             bubble_down(node)     else:         reassignprnt(None) 


Category: python Time: 2016-07-28 Views: 0
Tags: heap python tree

Related post

  • Python boids implementation 2016-01-31

    I am trying to implement a fairly basic boids simulation in python. My goal is to have a simulation with a basic predator prey setup. I found some pseudocode (can't post more than two links but it is the first result if you google boids pseudocode) a

  • Why do these Python XTEA implementations require different deltas? 2013-12-23

    I once needed to an XTEA snippet to from C++ to Python and it did not work properly. I then found a function on and noticed that it looks almost exactly like mine, with one exception - for some reason, its "delta" variable was ch

  • Treap implementation in C 2014-05-12

    I was needed a SET-like data structure written in pure C for some university class, so I've implemented a simple one - the Treap (or cartesian tree). Please check if everything is okay (actually, I'm not sure that there isn't a memory leak there). ca

  • Python Vector implementation that acts as a class and also a collection of staticmethods 2014-06-21

    Recently I've been wondering about ways of implementing objects in code that can be represented by other primitives. An example of this is a Vector, which can be represented by a Vector\$N\$D where \$N\$ is the dimension of vector, or it can be repre

  • Python DefaultDict implementation in JavaScript 2015-02-08

    I found Python's defaultdict and OrderedDict incredibly useful, hence I attempted an implementation in JavaScript. As JavaScript objects only supports string as key, it is not as powerful as the Python version. Can anyone suggest a way of using an ob

  • C# Treap implementation 2015-10-20

    I recently developed a simple treap data structure in C#. In the future, I may have the class extend IDictionary. For now, I only expose a public accessor and a delete method. public TValue this[TKey key] { get { return Get(root, key).Value; } set {

  • Simple tool to test my h2c implementation [on hold] 2016-02-17

    As a part of my studies, I decided to write an HTTP/2 server that is capable of simply serving static files. I have to write it in C, which I have very little experience with, so I decided to go with h2c (uses TCP), not h2 (uses TLS). I need some too

  • Yet another Pythonic range implementation for C++ 2016-02-23

    I recently had the need to loop from zero to some limit only known at runtime. Instead of writing: for(int i = 0; i < limit; ++i) { // Some repetitive thing } I wanted to write something similar to what I often use in Python and D: for i in range(0,

  • Should I use this very short Python Quicksort implementation? 2016-07-05

    def quicksort(N): if len(N) < 2: return N else: less = quicksort([number for number in N[1:] if number < N[0]]) more = quicksort([number for number in N[1:] if number > N[0]]) return sum([less, [N[0]], more], []) print(quicksort([1, 9, 6, 10, 8,

  • Python property() implementation that caches getter while still allowing a setter 2013-05-31

    For a session implementation I needed a property that caches its getter (since it involves a database lookup) but still allows modifications (e.g. assigning a new user and storing that user's id in the session). To make this as comfortable as possibl

  • Use python to implement a async notification system 2016-01-18

    I have been troubled by a design question. I want to implement a small service that looks like a mail office. It will accept clients request(in the request it has the message to deliver and destination url info). After that I will help the client to

  • Is there something wrong with this python code? [on hold] 2016-02-10

    This is a homework assignment i gotta do, super basic but im having trouble ;/ Objectives: Demonstrate use of the Python while-statement and if-statement. Description: Write a Python program that repeatedly reads user input and prints a result based

  • Noob Python API Call [on hold] 2016-02-11

    I will preface this with the disclaimer that I am a total programming noob. I'm just trying to write a basic Python script that will make an API call using a key and a "secret" (HMAC-SHA512). In my beginner, rudimentary code I'm just trying to f

  • object detection in python using opencv [on hold] 2016-02-11

    I would like to know which is the most efficient and simplest algorithm to detect an object (other than face) which varies in color and shape using a web-camera? Can I have the complete code in python which can be used in OpenCV with explanation?

  • wget using Python throws IOError [on hold] 2016-02-12

    I have a bunch of links in an array, looping through them and passing it to throws this error: Traceback (most recent call last): File "<stdin>", line 2, in <module> File "/usr/local/lib/python2.7/dist-package

  • Calling a different python class object [on hold] 2016-02-15

    class A(object): some class attributes some class methods class ATest(object): some class attributes (same as class A) some class methods (same as Class A) I have a few code lines like so: flag = 1 a = A() a.attribute = "some value" # set value

  • raw_input() function shows a syntax error in Python 2.7 [on hold] 2016-02-17

    num=input('Enter 'h' to indicate the guess is too high. Enter 'l' to indicate the guess is too low. Enter 'c' to indicate I guessed correctly.') This statement encountered an error as follows: File "c:\users\user\appdata\local\temp\"

  • Python For Loops [on hold] 2016-03-01

    How would I loop over two lists random lists in python and determine if an element appears in it twice. It is preferred that a for loop is used The two lists: list_1 = random.sample(range(1,100),random.randint(1,20)) list_2 = random.sample(range(1,10

  • Filter the Feature Layer parameter in Python Script Tool [on hold] 2016-03-04

    I have a Python script tool where I have a parameter of type Feature Layer because I want to have the already opened layers as a dropdown list. I was wondering if there is a way to filter this Feature Layer parameter dropdown list in order to show Po

iOS development

Android development

Python development

JAVA development

Development language

PHP development

Ruby development


Front-end development


development tools

Open Platform

Javascript development

.NET development

cloud computing


Copyright (C), All Rights Reserved.

processed in 0.275 (s). 13 q(s)