The soft heap: An approximate priority queue with optimal error rate

A simple variant of a priority queue, called a soft heap, is introduced. Th e data structure supports the usual operations: insert, delete, meld, and f indmin. Its novelty is to beat the logarithmic bound on the complexity of a heap in a comparison-based model. To break this information-theoretic barr ier, the entropy of the data structure is reduced by artificially raising t he values of certain keys. Given any mixed sequence of n operations, a soft heap with error rate epsilon (for any 0 < <epsilon> less than or equal to 1/2) ensures that, at any time, at most En of its items have their keys rai sed. The amortized complexity of each operation is constant, except for ins ert, which takes O(log 1/epsilon) time. The soft heap is optimal for any va lue of epsilon in a comparison-based model. The data structure is purely po inter-based. No arrays are used and no numeric assumptions are made on the keys. The main idea behind the soft heap is to move items across the data s tructure not individually, as is customary, but in groups, in a data-struct uring equivalent of "car pooling." Keys must be raised as a result, in orde r to preserve the heap ordering of the data structure. The soft heap can be used to compute exact or approximate medians and percentiles optimally. It is also useful for approximate sorting and for computing minimum spanning trees of general graphs.