Soft heap

In computer science, a soft heap is a variant on the simple heap data structure that has constant amortized time complexity for 5 types of operations. This is achieved by carefully "corrupting" (increasing) the keys of at most a constant fraction of values in the heap.

Definition and performance

The constant time operations are:

create(S): Create a new soft heap

insert(S, x): Insert an element into a soft heap

meld(S, S'): Combine the contents of two soft heaps into one, destroying both

delete(S, x): Delete an element from a soft heap

findmin(S): Get the element with minimum key in the soft heap

Other heaps such as Fibonacci heaps achieve most of these bounds without any corruption, but cannot provide a constant-time bound on the critical delete operation. The amount of corruption can be controlled by the choice of a parameter

ε

{\displaystyle \varepsilon }

, but the lower this is set, the more time insertions require: expressed using Big-O notation, the amortized time will be

O

(

log

⁡

1

/

ε

)

{\displaystyle O(\log 1/\varepsilon )}

for an error rate of

ε

{\displaystyle \varepsilon }

. Some versions of soft heaps allow the create, insert, and meld operations to take constant time in the worst case, producing amortized rather than worst-case performance only for findmin and delete. As with comparison sort, these algorithms access the keys only by comparisons; if arithmetic operations on integer keys are allowed, the time dependence on

ε

{\displaystyle \varepsilon }

can be reduced to

O

(

log

⁡

log

⁡

1

/

ε

)

{\displaystyle O(\log \log 1/\varepsilon )}

or (with randomization)

O

(

log

⁡

log

⁡

1

/

ε

)

{\textstyle O({\sqrt {\log \log 1/\varepsilon }})}

.

More precisely, the error guarantee offered by the soft heap is the following: each soft heap is initialized with a parameter

ε

{\displaystyle \varepsilon }

, chosen between 0 and 1/2. Then at any point in time it will contain at most

ε

⋅

n

{\displaystyle \varepsilon \cdot n}

corrupted keys, where

n

{\displaystyle n}

is the number of elements inserted so far. Note that this does not guarantee that only a fixed percentage of the keys currently in the heap are corrupted: in an unlucky sequence of insertions and deletions, it can happen that all elements in the heap will have corrupted keys. Similarly, there is no guarantee that in a sequence of elements extracted from the heap with findmin and delete, only a fixed percentage will have corrupted keys: in an unlucky scenario only corrupted elements are extracted from the heap.