Meta

• License: Apache v2
• Author:Daniel Richard Stromberg

Classifiers

• Development Status
  • 5 - Production/Stable
• Intended Audience
  • Developers
• Programming Language
  • Python :: 2.7
  • Python :: 3

A set of python modules implementing treaps in pure python is provided.

See also my pyx_treap module, which implements treaps in Cython.

Treaps perform most operations in O(log2(n)) time, and are innately sorted.They’re very nice for keeping a collection of values that needs toalways be sorted, or for optimization problems in which you need to findthe p best values out of q, when p is much smaller than q.

A module is provided for treaps that enforce uniqueness.

Example use:.. code-block:: python

>>> import treap>>> t = treap.treap()>>> for i in range(6):...     t[i] = 2**i...>>> list(t)[0, 1, 2, 3, 4, 5]>>> print(t)0                                                         5/319487918/32_1                         2/861020069/4__                                                 _______________2         1/1135044777/2_                 3/1142319761/8_                 _______________                 _______________3 0/1473918015/1_ _______________ _______________ 4/2019165697/16 _______________ _______________ _______________ _______________>>> list(t.items())[(0, 1), (1, 2), (2, 4), (3, 8), (4, 16), (5, 32)]>>>

Another example:.. code-block:: python

>>> import treap>>> t = treap.treap()>>> import random>>> for i in range(20):...    t[random.random()] = i...>>> list(t)[0.011795687154763312, 0.0695864396266509, 0.15741892655439682, 0.18718082546304682, 0.1910965922423038, 0.22849105220538402, 0.276078590851345, 0.3166512089228003, 0.3456516881327997, 0.3543869818366584, 0.4022879538597536, 0.4519316126668157, 0.46329639459896466, 0.4873225275394878, 0.5866856381825849, 0.6403758625610735, 0.6936888466959068, 0.7843975080768091, 0.8888622013819216, 0.9047894146828958]>>> t.find_min()0.011795687154763312>>> t.find_max()0.9047894146828958

Verified details

Maintainers

dstromberg

Unverified details

Project links

• Homepage

• Download URL:treap-2.0.10.tar.gz
• Upload date: Mar 12, 2021
• Size: 8.5 kB
• Tags: Source
• Uploaded using Trusted Publishing? No
• Uploaded via: twine/1.13.0 pkginfo/1.5.0.1 requests/2.22.0 setuptools/41.1.0 requests-toolbelt/0.9.1 tqdm/4.33.0 CPython/3.6.9

See more details on using hashes here.