Skip to main content

Python Soft Heap Implementation

Project description

Soft Heap in Python

This library is a full python implementation of Bernard Chazelle's soft heap [1].

The soft heap is a heap-like data structure which gives all heap operations a constant runtime, with the exception of insert. However, in order to maintain this seemingly impossible runtime, some of the data is "corrupted". The result of this is that insert takes O(log 1/e) where e is the rate of corruption.



To get started, import the module. We'll also import random for this example.

from softheap import *
import random

The soft heap requires one input, the error rate r. The number of corrupted nodes in the heap is inversely proportional to r.

s = SoftHeap(2)

We can test the heap by randomly inserting 100 elements into the heap.

arr = list(range(100))

for a in arr:

Now when we deletemin repeatedly, the output will be approximately sorted.

output = []

for b in range(len(arr))


This takes O(n log 1/e) time.


Use pip to install softheap. Via the command line:

pip install softheap

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for softheap, version 0.2
Filename, size File type Python version Upload date Hashes
Filename, size softheap-0.2-py2-none-any.whl (3.8 kB) File type Wheel Python version py2 Upload date Hashes View
Filename, size softheap-0.2.tar.gz (3.5 kB) File type Source Python version None Upload date Hashes View

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring DigiCert DigiCert EV certificate Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page