Std.Heap.Heap

type

This declaration introduces a public type.

What it does

A collection that always knows its smallest element.

A sorted array knows its smallest too, but paying to keep everything in

order is paying for an answer nobody asked for: a scheduler wants the next

task, not the whole schedule. Sorting the array again after each insertion

costs far more than this, and scanning an unsorted one for the minimum

costs more on every read.

The shape is a tree whose every node is smaller than the nodes beneath it,

so the smallest element is the root and reading it is immediate. Adding is

one comparison. Removing the root leaves its children loose, and they are

rejoined in two passes — pairing them up, then folding the pairs together —

which is what keeps the tree from degenerating into a list under repeated

removal.

Read the signature

• This declaration has no value signature because it introduces a type or trait.