title: Soft heaps: what is corruption and why is it useful?
body: <p>I recently read Bernard Chazelle's paper "The Soft Heap, An Approximate Priority Queue with Optimal Error Rate by Bernard Chazelle" (<a href="http://www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-heap.pdf">http://www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-heap.pdf</a>)</p>
  
  <p>The paper talks a lot about "corruption." What is corruption, how do elements get corrupted, and how does it help you?</p>
  
  <p>I have spent a lot of time reading through the paper and Googling and this still doesn't make sense.</p>