jasondavies / softheap.js

A JavaScript implementation of Chazelle's Soft Heaps; based on Louis Wasserman's Java implementation.

softheap.js

A JavaScript implementation of A simpler implementation and analysis of Chazelle’s Soft Heaps by Haim Kaplan and Uri Zwick.

Based on a Java implementation by Louis Wasserman.

A soft heap is a variant on the simple heap data structure that has constant amortised time for 5 types of operations:

• create
• insert
• meld
• delete
• findmin

The term "soft heap" stems from the fact that a fixed percentage of values have their keys "corrupted". The purpose of these corruptions is to lower the information entropy of the data, enabling the data structure to break through information-theoretic barriers regarding heaps.