A soft heap is a data structure that acts like a priority queue, but which can corrupt some of the priorities.
Soft heaps were introduced by Chazelle as a building block in a fast MST algorithm. They work like regular priority queues except that they can corrupt the priorities. Specifically, for some constant ε, the soft heap ensures that at most εn of the elements in the soft heap will have their priorities corrupted by increasing them some amount.
Soft heaps have also been used to give an alternative O(n)-time selection algorithm.
