Heaps

Heaps, also known as priority queues, provide efficient access to the minimum element in a collection, and an efficient delete-the-minimum operation as well as a merge operation that takes two heaps and returns one.

We define "minimum" with respect to an Ordering type parameter, so heaps are parameterized by both the element type and the ordering.

Heaps in PureFun.jl inherit from the abstract type PureFun.PFHeap. The full interface:

push(xs, x) returns a new heap containing x as well as all elements in xs
minimum
popmin
merge

Heaps iterate in sorted order, so first(xs::Heap) == minimum(xs)

If not specified, the ordering for a heap defaults to Base.Order.Forward. Heap constructors are like the constructors for lists and queues, but take the ordering as an additional optional argument.

`Pairing.Heap` $\S{5.5}$

The Pairing.Heap is very fast, but requires occasional expensive rebalancing operations to maintain efficient access to the minimum element, and should be used when the data structure has only a single logical future (see the discussion in Queues for more information about this concept). Otherwise, try the SkewBinomial.Heap or the BootstrappedSkewBinomial.Heap

PureFun.Pairing.Heap — Type

Pairing.Heap{T}(o::Base.Order.Ordering=Base.Order.Forward)
Pairing.Heap(iter, ord=Base.Order.Forward)

Pairing heaps ($\S{5.5}$):

... are one of those data structures that drive theoreticians crazy. On the one hand, pairing heaps are simple to implement and perform extremely well in practice. On the other hand, they have resisted analysis for over ten years!

push, merge, and minimum all run in $\mathcal{O}(1)$ worst-case time. popmin can take $\mathcal{O}(n)$ time in the worst-case. However, it has been proven that the amortized time required by popmin is no worse than $\mathcal{O}(\log{}n)$, and there is an open conjecture that it is in fact $\mathcal{O}(1)$. The amortized bounds here do not apply in persistent settings. For heaps suited to persistent use-cases, see PureFun.SkewBinomial.Heap and PureFun.BootstrappedSkewBinomial.Heap

Examples

julia> using PureFun, PureFun.Pairing
julia> xs = [5, 3, 1, 4, 2];

julia> Pairing.Heap(xs)
5-element PureFun.Pairing.NonEmpty{Int64, Base.Order.ForwardOrdering}
1
2
3
4
5


julia> Pairing.Heap(xs, Base.Order.Reverse)
5-element PureFun.Pairing.NonEmpty{Int64, Base.Order.ReverseOrdering{Base.Order.ForwardOrdering}}
5
4
3
2
1


julia> empty = Pairing.Heap{Int}(Base.Order.Reverse);
julia> reduce(push, xs, init=empty)
5-element PureFun.Pairing.NonEmpty{Int64, Base.Order.ReverseOrdering{Base.Order.ForwardOrdering}}
5
4
3
2
1

source

`SkewBinomial.Heap` $\S{9.3.2}$

PureFun.SkewBinomial.Heap — Type

SkewBinomial.Heap{T}(o=Base.Order.Forward)
SkewBinomial.Heap(iter, o=Base.Order.Forward)

The Skew Binomial Heap $\S{9.3.2}$ is a twist on the Binomial Heap: by basing tree sizes on skew-binary (rather than binary) numbers, pushing a new element into a skew binomial heap is worst-case $\mathcal{O}(1)$ (as opposed to $\mathcal{O}(\log{}n)$ for binomial heaps). merge, popmin, and minimum are worst-case $\mathcal{O}(\log{}n)$. See also PureFun.BootstrappedSkewBinomial.Heap, which uses structural abstraction to improve minimum and merge to worst-case $\mathcal{O}(1)$

source

`BootstrappedSkewBinomial.Heap` $\S{10.2.2}$

PureFun.BootstrappedSkewBinomial.Heap — Type

BootstrappedSkewBinomial.Heap{T}(ord=Base.Order.Forward)
BootstrappedSkewBinomial.Heap(iter, ord=Base.Order.Forward)

Section $\S{10.2.2}$ of Purely Functional Data Structures demonstrates how to use structural abstraction to take a heap implementation with $\mathcal{O}(1)$ push and improve the running time of merge and minimum to $\mathcal{O}(1)$. The BootStrappedSkewBinomial.Heap uses the technique on the PureFun.SkewBinomial.Heap.

source