This is a guest post by Chris Okasaki. It was initially published as the design document behind scads. It is being republished here with the permission of the original author. A heap (or priority queue) is a collection of elements ordered by some Ordering, optimized for retrieving the first element according to that ordering. Duplicate elements are allowed. Applications vary in whether they need the first element to be the smallest or the biggest element according to the ordering, so both var...
