python软堆实现
softheap的Python项目详细描述
python中的软堆
这个库是bernard chazelle的软堆的完整python实现[1]。
软堆是一种类似堆的数据结构，它为所有堆操作提供一个常量运行时，但insert除外。然而，为了维护这个看似不可能的运行时，一些数据被“损坏”。其结果是insert takes o（log 1/e），其中e是损坏率。
[1]http://www.cs.cmu.edu/afs/cs/academic/class/15859-f05/www/documents/p1012-chazelle.pdf
使用量
要开始，请导入模块。我们还将为这个示例导入random。
from softheap import *
import random
软堆需要一个输入，即错误率r。堆中损坏的节点数与r成反比。
s = SoftHeap(2)
我们可以通过在堆中随机插入100个元素来测试堆。
arr = list(range(100))
random.shuffle(arr)
for a in arr:
s.insert(a)
output = []
for b in range(len(arr))
output.append(s.deletemin())
print(output)
这需要O（N log 1/E）时间。
安装
使用pip安装软堆。通过命令行：
pip install softheap
欢迎加入QQ群-->： 979659372
