Reference

QuickHeaps.AbstractBinaryHeap{T,O}

is the super-type of binary heaps in QuickHeaps whose values have type T and whose ordering has type O.

The following methods are available for a binary heap h (those which modify the heap contents re-order heap values as needed to maintain the heap structure):

pop!(h)        # deletes and returns root value of heap h
push!(h, x)    # pushes value x in heap h
empty!(h)      # empties heap h
isempty(h)     # yields whether heap h is empty
delete!(h, i)  # deletes i-th value from heap h
peek(h)        # yields root value of heap h without deleting it
first(h)       # idem
setroot!(h, x) # same as h[1] = x, replaces root value of heap h by x

A binary heap h behaves like an abstract vector (with 1-based linear indices), in particular:

length(h)   # the number of values in heap h
h[i]        # the i-th value of heap h
h[i] = x    # set the i-th value of heap h and heapify h

Note that h[1] is the root value of the heap h and that setting a value in the heap may trigger reordering of the values to maintain the binary heap structure. In other words, after doing h[i] = x, do not assume that h[i] yields x.

Operations that modify the heap, like deletion by delete!(h,i), insertion by h[i] = x, pushing by push!(h,x), and extracting by pop!(h) are of complexity O(1) in the best case, O(log(n)) in the worst case, with n = length(h) the number of values in the heap h. Retrieving a given value with peek(h), first(h), or h[i] is always of complexity O(1).

BinaryHeap{T}([o::Ordering = Forward,][ vals::AbstractVector])

yields an empty binary heap whose values have type T and with ordering specified by o. For example, a min-heap (resp. a max-heap) is built if o specifies forward (resp. reverse) ordering.

An optional vector vals storing the initial values of the binary heap can be specified. These values in vals need not be ordered, the BinaryHeap constructor automatically takes care of that. If vals is a Vector{T} instance, the binary-heap will be directly built into vals. Call BinaryHeap(copy(vals)) to create a binary heap with its own storage.

Arguments o and vals may be specified in any order.

Method sizehint!(h,n) may be called to anticipate that the heap may contains n values.

FastBinaryHeap{T}([o::Ordering = FastForward,][ vals::AbstractVector])

yields a fast binary heap. Compared to BinaryHeap{T}(...), the default ordering is FastForward and the array backing the storage of the heap values is never reduced to improve performances in some cases. You may call resize!(h) to explicitly reduce the storage of fast binary-heap h to its minimum.

heapify([o=Base.Forward,] A, n=length(A))

yields an array with the n first values of array A stored in a binary heap structure of ordering specified by o. The storage of the returned heap is a different array than A. Arguments may be specified in any order.

heapify!(h) -> h

reorders the values in the binary heap h in-place. This method should be called to initialize the heap or to re-order the heap if its contents have been modified by other methods than pop! or push!.

The method can be called at a lower level to heapify (part of) an array storing the heap values:

heapify!([o=Base.Forward,] A, n=length(A)) -> A

reorders the n first elements of array A in-place to form a binary heap according to the ordering specified by o. The array A must have 1-based linear indexing. Arguments may be specified in any order.

QuickHeaps.heapify_down!(o, A, i, x=A[i], n=lengh(A)) -> A

stores the value x in the i-th entry of the binary heap built into the n first elements of array A with ordering o and, if needed, moves down the inserted value to maintain the binary heap structure.

This method is called to heapify an array in order to initialize or rebuild the heap structure or to replace the value of the root value of the heap and update the heap structure.

QuickHeaps.heapify_up!(o, A, i, x=A[i]) -> A

stores the value x in the i-th entry of the binary heap built into the i first elements of array A with ordering o and, if needed, moves up the value to maintain the heap structure.

isheap([o=Base.Forward,], A, n=length(A))

yields whether the n first elements of array A have a binary heap structure ordered as specified by o. Arguments may be specified in any order.

isheap(obj; check=false)

yields whether object obj is a binary heap. If keyword check is true, the internal structure of obj is checked; otherwise, the type of obj is trusted to determine whether it is a binary heap.

QuickHeaps.unsafe_heapify_down!(o, A, i, x=A[i], n=lengh(A))

This method is a fast but unsafe version of QuickHeaps.heapify_down! which assumes that all arguments are correct, that is A implements 1-based linear indexing, 0 ≤ n ≤ lengh(A), and 1 ≤ i ≤ n.

QuickHeaps.unsafe_heapify_up!(o, A, i, x=A[i])

This methods is a fast but unsafe version of QuickHeaps.heapify_up! which assumes that all arguments are correct, that is A implements 1-based linear indexing and 1 ≤ i ≤ length(A).

QuickHeaps.unsafe_grow!(h, n) -> A

grows the size of the binary heap h to be n and returns the array A backing the storage of the values. This method is unsafe because it does not check its arguments and because it breaks the binary heap structure of the array of values.

This method is called by push! to grow the size of the heap and shall be specialized for any concrete sub-types of QuickHeaps.AbstractBinaryHeap.

QuickHeaps.unsafe_grow!(pq, n) -> pq

grows the size of the binary heap backing the storage of the nodes of the priority queue pq to be n and returns the priority queue object.

QuickHeaps.unsafe_shrink!(h, n)

shrinks the size of the binary heap h to be n. This method is unsafe because it does not check its arguments.

This method is called by delete! to eventually reduce the size of the heap and shall be specialized for any concrete sub-type of QuickHeaps.AbstractBinaryHeap.

QuickHeaps.unsafe_shrink!(pq, n)

shrinks the size of the binary heap backing the storage of the nodes of the priority queue pq to be n.

QuickHeaps.AbstractPriorityQueue{K,V,O}

is the super type of priority queues with nodes consisting in pairs of keys of type K, priority values of type V, and ordering of type O<:Base.Ordering.

Priority queues implement an API similar to dictionaries with the additional feature of maintaining an ordered structure so that getting the node of highest priority costs O(1) while pushing a node costs O(log(n)) with n the size of the queue. See online documentation for more details.

QuickHeaps provides two concrete types of priority queues: PriorityQueue for any kind of keys and FastPriorityQueue for keys which are analoguous to array indices.

PriorityQueue{K,V}([o=Forward,] T=Node{K,V})

yields a priority queue for keys of type K and priority values of type V. Optional arguments o::Ordering and T<:AbstractNode{K,V} are to specify the ordering of values and type of nodes to store key-value pairs. Type parameters K and V may be omitted if the node type T is specified.

Having a specific node type may be useful to specialize the Base.lt method which is called to determine the order.

If keys are analoguous to array indices (linear or Cartesian), FastPriorityQueue may provide a faster alternative.

FastPriorityQueue{V}([o=Forward,] [T=Node{Int,V},] dims...)

yields a priority queue for keys analoguous of indices in an array of size dims... and priority values of type V. Optional arguments o::Ordering and T<:AbstractNode{Int,V} are to specify the ordering of values and type of nodes to store key-value pairs (the key is stored as a linear index of type Int). Type parameter V may be omitted if the node type T is specified.

See PriorityQueue if keys cannot be assumed to be array indices.

dequeue!(pq) -> key

removes the root node from the priority queue pq and returns its key.

Also see dequeue_node! and dequeue_pair!.

dequeue_node!(pq) -> node

removes and returns the root node from the priority queue pq.

Also see dequeue! and dequeue_pair!.

dequeue_pair!(pq) -> (key => val)

removes the root node from the priority queue pq and returns it as a key-value Pair. This is the same as pop!(pq).

Also see dequeue! and dequeue_node!.

QuickHeaps.AbstractNode{K,V}

is the super-type of nodes with a key of type K and a value of type V. Nodes can be used in binary heaps and priority queues to represent key-value pairs and specific ordering rules may be imposed by specializing the Base.lt method which is by default:

Base.lt(o::Ordering, a::T, b::T) where {T<:QuickHeaps.AbstractNode} =
    lt(o, QuickHeaps.get_val(a), QuickHeaps.get_val(b))

QuickHeaps.Node{K=typeof(k),V=typeof(v)}(k,v)

yields a node storing key k and value v. Optional type parameters K and V are the respective types of the key and of the value.

See also QuickHeaps.AbstractNode, QuickHeaps.AbstractPriorityQueue.

get_key(x::QuickHeaps.AbstractNode) -> k

yields the key k of node x. This method may be specialized for any sub-types of QuickHeaps.AbstractNode.

Also see QuickHeaps.get_val.

QuickHeaps.get_val(x::QuickHeaps.AbstractNode) -> v

yields the value v of node x. This method may be specialized for any sub-types of QuickHeaps.AbstractNode.

Also see QuickHeaps.get_key.

FastForwardOrdering

is the singleton type for fast forward ordering without considering NaN's.

default_ordering(T)

yields the default ordering for an ordered data structure of type T. This method shall be specialized for each ordered data structure.

has_bad_values(A[, isbad])

yields whether array A has bad values according to predicate isbad. For arrays with floating-point values, isbad default to isnan if unspecified. For integer-valued arrays, this function always returns false if isnan is unspecified.

has_standard_linear_indexing(A)

yields whether array A implements standard linear indexing (1-based).

Quickheaps.heap_index(pq, k) -> i

yields the index of the key k in the binary heap backing the storage of the nodes of the priority queue pq. If the key is not in priority queue, i = 0 is returned, otherwise i ∈ 1:n with n = length(pq) is returned.

The heap_index method is used to implement haskey, get, and delete! methods for priority queues. The heap_index method shall be specialized for any concrete sub-types of QuickHeaps.AbstractPriorityQueue.

in_range(i, len::Integer)

yields whether 1 ≤ i ≤ len.

in_range(i, A::Array)

yields whether i is a valid linear index of array A.

in_range(i, R::AbstractUnitRange{<:Integer})

yields whether i is in the range R.

is_one_based_unit_range(itr)

yields whether iterator itr is a 1-based unit range.

QuickHeaps.linear_index(pq, k)

converts key k into a linear index suitable for the fast priority queue pq. The key can be a linear index or a multi-dimensional index (anything accepted by to_indices). The current settings for bounds checking are used.

QuickHeaps.nodes(pq)

yields the array backing the storage of the nodes of priority queue pq.

QuickHeaps.index(pq) -> I

yields the object I storing the key-index association in priority queue pq. This object can be used as I[key] to yield , for a given key, the index in QuickHeaps.nodes(pq), the associated binary heap.

QuickHeaps.storage(h)

yields the array backing the storage of the values in the binary heap h.

This method may be specialized for custom binary heap types.

QuickHeaps.ordering(h)

yields the ordering of the values in the binary heap h.

This method may be specialized for custom binary heap types.

QuickHeaps.ordering(pq) -> o

yields the object o specifying the ordering of priority values in the priority queue pq.

setroot!(h, x) -> h

replaces the value of the root note in heap h by x. This is similar to h[1] = x but a bit faster.

Quickheaps.to_key(pq, k)

converts the key k to the type suitable for priority queue pq.

Quickheaps.to_node(pq, k, v)

converts the the key k and the value v into a node type suitable for priority queue pq.

Quickheaps.to_val(pq, v)

converts the value v to the type suitable for priority queue pq.

typename(x)

yields a short string describing the type of object x. Argument may also be the object type.