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).

Call Base.Order.Ordering(h) to retrieve the ordering object o for the binary heap h.

h = BinaryHeap{T}([o::Base.Order.Ordering = TotalMin,][ vals::AbstractVector])

Build an empty binary heap whose values have type T and with ordering specified by o.

The method Base.Order.lt(o,x::T,y::T) is called to determine the order of values x and y in the heap. The default ordering, TotalMin, yields a min-heap object; with TotalMax ordering, a max-heap object is returned.

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.

h = FastBinaryHeap{T}([o::Base.Order.Ordering = TotalMin,][ vals::AbstractVector])

Build a fast binary heap. Compared to BinaryHeap{T}(...), the array backing the storage of the heap values is never automatically 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=TotalMin,] 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=TotalMin,] 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=TotalMin,], 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 entries 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 entries of the priority queue pq to be n.

QuickHeaps.AbstractPriorityQueue{K,V,O}

is the super type of priority queues with ordering of type O<:Base.Order.Ordering and storing keys of type K associated priority values of type V.

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

Priority queues behave like dictionaries with the additional feature of automatically maintaining an ordered structure according to the priority queue ordering and the entry values. For a priority queue pq, retrieving the root entry, that is the pair key => val of highest priority, without removing it costs O(1) and is done by:

peek(pq) -> (key => val)

Retrieving the value of an entry given its key has also an O(1) complexity and is done by one of:

pq[key...] -> val
getindex(pq, key...) -> val
get(pq, key, def) -> val_at_key_or_def

Changing the content of the priority queue has a complexity of O(log(n)) with n = length(pq) the number of queued entries. This includes removing the entry at key by:

delete!(pq, key) -> pq
pop!(pq, key) -> val
pop!(pq, key, def) -> val_or_def

removing the root entry by:

pop!(pq)          # -> root entry as a `key=>val` pair
dequeue!(pq)      # -> key of root entry
dequeue_pair!(pq) # -> root entry as a `key=>val` pair

or setting/changing an entry with a given key and value val by one of:

pq[key] = val
enqueue!(pq, key => val)
push!(pq, key => val)

Call Base.Order.Ordering(pq) to retrieve the ordering object o for the priority queue pq.

PriorityQueue{K,V}(o=TotalMin)

yields a priority queue for keys of type K and priority values of type V. Optional argument o::Ordering specifies the ordering of values.

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

FastPriorityQueue{V}(o=TotalMin, dims...)

yields a priority queue for keys analogous of indices in an array of size dims... and priority values of type V. Optional argument o::Ordering specifies the ordering of values. The keys are stored as linear indices of type Int.

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

dequeue!(pq) -> key

Remove the root entry from the priority queue pq and return its key.

You may call dequeue_pair!(pq) to dequeue the root entry as a key-value pair.

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

Remove the root entry from the priority queue pq and return it as a key-value pair. This is the same as pop!(pq).

Also see dequeue!.

pq[key...] = val
setindex!(pq, val, key...) -> pq
enqueue!(pq, key, val) -> pq
enqueue!(pq, key => val) -> pq
push!(pq, key => val) -> pq

Set the value val stored by the priority queue pq at index key automatically maintaining the partial ordering of pq.

QuickHeaps.FastMinOrdering <: Base.Order.Ordering
const FastMin = QuickHeaps.FastMinOrdering()

Singleton for min ordering. This ordering is faster than TotalMin but leaves indefinite the order of NaN values.

QuickHeaps.FastMinOrdering is the type of FastMin.

Also see FastMax.

FastMax

Singleton for max ordering. This ordering is faster than TotalMax but leaves indefinite the order of NaN values.

QuickHeaps.FastMaxOrdering is an alias to the type of FastMax.

Also see FastMin.

TotalMin

Singleton for total min ordering considering NaN's as greater than any other floating-point value, and missing to be greater than anything else. With this ordering, values are sorted in ascending order, followed by NaN then missing values.

TotalMin is similar to the default ordering in most Julia algorithms and which is implemented by isless. However, for arrays of floating-point values with 50% of NaN's, TotalMin is nearly as fast as (19%) using < and is almost twice faster (82%) than isless. This speed-up is obtained by using non-branching bitwise operators instead of logical operators.

QuickHeaps.TotalMinOrdering is the type of TotalMin.

Also see TotalMax.

TotalMax

Singleton for total max ordering. With this ordering, values are sorted in decreasing order, followed by NaN then missing values.

QuickHeaps.TotalMaxOrdering is the type of TotalMax.

Also see TotalMin.

QuickHeaps.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.

QuickHeaps.heap_index(pq, key) -> i::Int

Return the index i corresponding to key in the binary heap backing the storage of the entries 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.

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.

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.