软堆:什么是损坏?为什么它有用？
软堆:什么是损坏?为什么它有用？
提问于 2014-10-01 00:55:50
我最近读了伯纳德·查泽尔的论文“软堆，具有最佳错误率的近似优先级队列”(http://www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-heap.pdf)
这篇论文谈了很多关于“腐败”的问题。什么是腐败，元素是如何被破坏的，它对你有什么帮助？
我花了很多时间通读这篇论文并用谷歌搜索，但这仍然没有意义。
回答 1
Stack Overflow用户
发布于 2014-10-01 01:04:38
答案在第二页：
“软堆可以在任何时候增加某些键的值。这样的密钥以及相应的项被称为损坏的。损坏完全由数据结构决定，用户无法控制它。当然，findmin会返回最小的当前密钥，该密钥可能已损坏，也可能未损坏。这样做的好处是速度:在堆更新期间，项以“拼车”的形式以包的形式一起传输，以节省时间。从信息论的观点来看，损坏是一种降低存储在数据结构中的数据的熵的方法，从而促进其处理。熵被定义为以二为底的不同键分配的数量的对数(即，键分配上的均匀分布的熵)。为了查看这个想法的可靠性，将它推到它的极限，并观察到如果每个键通过将其值提高到`而损坏，那么键集将具有零熵，并且我们可以在固定时间内平凡地执行所有操作。有趣的是，软堆表明熵不需要降到零，复杂度就会变得恒定。
这是一种弄巧成拙的数据结构吗？
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/26126170
复制相关文章
相似问题
腾讯云开发者
