heap - sellout/data-structure-zoo GitHub Wiki

A heap is an ADT (despite Wikipedia’s claim that it’s a data structure). It’s an ordered container that retrieves values in sorted order, based on some provided function. It adds the operations [[chop optimum]], [[merge]], [[peek optimum]], [[pop optimum!]], and [[push]]. It is distinct from a priority queue in that with a heap, the ordering is intrinsic to the value, whereas with a priority queue, there may be no way to determine the priority from the value.

The heap interface should provide an implementation of [[merge]] to cover the case of merging two different data structures. The implementation is O(n) at best (it could be worse, depending on the data structures involved), but in most cases, the data structures you’re merging should be the same, and in that case they probably provide a more efficient implementation.

fun merge a b {
  h = empty (class a)
  while (not (empty? b))
    h = push (peek b) h
    b = chop b
  h
}

fun merge! a b {
  while (not (empty? b))
    push! (pop! b) a
}

• Brodal queue – either
• rank-pairing heap –
• Fibonacci heap –
• pairing heap –
• binomial heap –
• binary heap –
• splay heap – pure