TrackingHeaps

TrackingHeaps

TrackingHeaps.TrackingHeaps — Module.

TrackingHeaps offers a heap with a tracking system for the stored values.

Inserting a value into a TrackingHeap returns a tracker for the value. The tracker can be used to access, update, and delete the value without searching for it first. Heap order do not allow for O(log m) search (where m is the number of values currently stored inside the heap), just for O(m) search, so this feature allow for some performance gain if you need to manipulate values anywhere in the heap (not just on top of the heap). Besides access, which is O(1), update and delete are O(log m) as they may need to rebalance the tree.

If the tracking system is not needed, there is little reason to use this heap.

I wrote this package because the MutableBinaryHeap of DataStructures.jl did not allow some behavior I wanted; behavior as:

  1. a non-top value can be deleted without being made top first;
  2. convenience methods allow to pop!/delete! stored values and immediatelly track! others, avoiding double-rebalancing;
  3. after a value is deleted, its tracker can be re-reused to re-insert that value or insert a new value (but this is not done automatically);
  4. the arity of the heap (binary, trinary, etc..) can be defined by the user (by parametric type) and inccur in minimal overhead (I hope);
  5. all the stored values are in a Vector{V} in heap order, for easy backdoor/hacking access;
  6. the integer type that is the tracker type can be defined by the user.
source
TrackingHeaps.MaxHeapOrder — Type.
MaxHeapOrder

The alternative type for the type parameter O (i.e., Order) of TrackingHeap. If used the heap will have the maximum value as top value.

See also: is_higher_than, TrackingHeap

source
TrackingHeaps.MinHeapOrder — Type.
MinHeapOrder

The default type for the type parameter O (i.e., Order) of TrackingHeap. If used the heap will have the minimum value as top value.

See also: is_higher_than, TrackingHeap

source
TrackingHeaps.NoTrainingWheels — Type.
NoTrainingWheels

The alternative type for the type parameter S (i.e., Safety) of TrackingHeap. Inform the heap methods avoid any checking theoretically giving the best speed.

See also: SafeFromYourself

source
TrackingHeaps.SafeFromYourself — Type.
SafeFromYourself

The default type for the type parameter S (i.e., Safety) of TrackingHeap. Inform the heap methods to use @assert to check for any possible inconsistencies, and throw KeyError tried to access/delete/update an non-existent key.

See also: NoTrainingWheels

source
TrackingHeaps.TrackingHeap — Type.
TrackingHeap{K, V, N, O, S} <: AbstractDict{K, V}

The type of a heap that has tracker/keys of type K (an integer), stored values of type V, that is N-ary (binary, trinary, etc...), with the order defined by O, and the safety level defined by S.

Equal values are allowed but, if more than one value could be the top value, then any of the equal values may be there (they can yet be distinguished by tracker).

The TrackingHeap implements (almost) all methods described in Dict interface, and can be seen as a Dict (with the special property of always allowing for fast access to the minimal/maximal value and its key). There is an AbstractHeap of DataStructures, but it was designed for heaps without key, and then an AbstractMutableHeap interface (for heaps with keys) was grafted into it. Also, inheriting such interface would make necessary that this package used DataStructures just for inheriting its abstract type.

source
TrackingHeaps.TrackingHeap — Method.
TrackingHeap(tracking_heap) # copy constructor
TrackingHeap(::Type{V}; kwargs = ...)

Constructs a TrackingHeap with default types for all type parameters except V (i.e., the stored values, that has no obvious default).

This constructor also accepts a variety of keyword arguments which allow to change the default type parameters and initialize the heap.

The constructor allow to initialize using: a values vector in heap order to be owned by the heap (no overhead, nor checking); a values iterable collection (the respective trackers should be assumed to be one(K):convert(K, length(number of initial values))); a pairs iterable collection. These options are mutually exclusive.

See also: MinHeapOrder, SafeFromYourself

Arguments

  • K: The tracker keys type. Default: typeof(length(T[])).
  • N: The N-arity of the heap. Default: binary (i.e, 2).
  • O: The ordering of the heap values. Default: MinHeapOrder.
  • S: The safety level of the heap methods. Default: SafeFromYourself.
  • init_val_heap: a Vector already in heap order. Default: empty.
  • init_val_coll: an initial collections of values to be copied. Default: empty.
  • init_pairs: an initial collection of pairs tracker-value to be copied. Default: empty.
source
TrackingHeaps.empty!! — Method.
empty!!(heap) -> heap

Delete all stored values efficiently (consider internals structure unused). O(1).

CAUTION: this resets which trackers are considered "never used", so a call to next_tracker or track! after it will return the first tracker a newly created TrackingHeap gives (and so on).

Do not guarantee that previous sizehint! or any vector growth have their effect negated.

See also: extract!, delete! track!

source
TrackingHeaps.extract! — Method.
extract!(heap, trck) -> sval

Delete the value referred by trck in the heap, and return it.

The trck can then be used to re-insert it, or to insert another value.

The heap may need to be rebalanced, so O(log m).

See also: delete!, empty!

source
TrackingHeaps.extract_and_push! — Method.
extract_and_push!(heap, old_trck, new_trck => new_sval) -> old_sval

Similar to extract_and_track! but let you define new_trck.

CAUTION: guarantee that the value referred by old_trck will be extracted and the new pair will be pushed but does not guarantee that the internal heap structure will end up in the same state as calling extract! followed by push!.

See also: extract_and_track!, extract!

source
TrackingHeaps.extract_and_track! — Method.
extract_and_track!(heap, old_trck, new_sval) -> (old_sval, new_trck)

Similar to calling extract! followed by track! but more optimized.

CAUTION: guarantee that the value referred by old_trck will be extracted and the new value will be tracked but does not guarantee that the internal heap structure will end up in the same state as calling extract! followed by track!.

See also: pop_and_track!, extract!, track!,

source
TrackingHeaps.is_higher_than — Method.
is_higher_than(HeapOrderType, x, y) :: Bool

To define an ordering that is not the stored value type (i.e., V) default, you can create a new empty type and extend the is_higher_than function with a method that takes such empty type and returns if x should be higher in the heap than y based on it (so you do not need to wrap the value type inside a new type for a different ordering).

Note that is_higher_than defaults to < and > instead of isless and !isless (that would be >=).

Also, if you do not want to provide a < and > for the stored value type, you can instead just define this function for ::Type{MinHeapOrder} (and/or ::Type{MaxHeapOrder}) and x-and-y of the specific types of the values compared.

See also: MinHeapOrder, MaxHeapOrder, TrackingHeap

source
TrackingHeaps.next_tracker — Method.
next_tracker(heap) -> trck

Return the same tracker the next call of track! would return, without modifying the heap in any way. O(1).

See also: track!

source
TrackingHeaps.pop_and_track! — Method.
pop_and_track!(heap, new_sval) -> ((top_sval, top_trck), new_trck)

Similar to calling pop! followed by track! but more optimized.

CAUTION: guarantee that the top will be popped and the new value will be tracked but does not guarantee that the internal heap structure will end up in the same state as calling pop! followed by track!.

See also: pop!, track!,

source
TrackingHeaps.pop_once_and_track_many! — Method.
pop_once_and_track_many!(heap, new_svals)::((top_sval,top_trck), new_trcks)

Similar to calling pop! once followed by many calls to track! but more optimized.

CAUTION: guarantee that the top will be popped and the new values will be tracked but does not guarantee that the internal heap structure will end up in the same state as it would by calling pop! followed by calls to track! (in the same order given in the array).

See also: pop!, track!, pop_and_track!

source
TrackingHeaps.renew_tracker! — Method.
renew_tracker!(heap, old_trck, new_trck = next_tracker(heap)) -> new_trck

Marks old_trck as unused, begins using new_trck to refer to the value previously pointed by old_trck, and returns new_trck.

Does not need any rebalancing, O(1), but may inccur in memory allocation if new_trck was never used. The new_trck can be a tracker already used in the past, but must not be in use at the moment.

See also: pop_and_track!, update!, next_tracker, extract_and_track!

source
TrackingHeaps.top — Method.
top(heap) -> (sval, trck)

Returns the "highest" value stored inside the heap and its tracker. O(1).

See also: is_higher_than

source
TrackingHeaps.track! — Method.
track!(heap, sval) -> trck

Insert a new sval into the heap and return a new "never used" tracker for it.

The return is the same the method next_tracker would give if called before track!. The heap may need to be rebalanced, so O(log m).

See also: pop_and_track!, next_tracker, empty!!

source
TrackingHeaps.update! — Method.
update!(heap, trck, new_value) -> heap
update!(heap, trck => new_value) -> heap

Update the value pointed by trck. O(log m).

Similar to setindex! but assumes trck exists, if it does not, gives a KeyError when S === SafeFromYourself, and undefined behaviour when S !== SafeFromYourself.

See also: setindex!

source
Base.delete! — Method.
delete!(heap, trck) -> heap

Delete the value referred by trck in the heap, and return the heap.

The trck can then be used to re-insert it, or to insert another value.

The heap may need to be rebalanced, so O(log m).

See also: extract!, pop!

source
Base.empty! — Method.
empty!(heap) -> heap

Delete all stored values efficiently (consider internals structure unused). O(1).

CAUTION: this does not reset which trackers are considered "never used", so a call to next_tracker before empty! and another after will return the same.

Do not guarantee that previous sizehint! or any vector growth have their effect negated.

See also: extract!, delete!, track!

source
Base.getindex — Method.
getindex(heap, trck) -> sval

Return the value referred by trck in heap. O(1).

Only check if the tracker key exists if S === SafeFromYourself.

See also: setindex!

source
Base.isempty — Method.
isempty(heap) :: Bool

Returns true if the heap has no values stored; false otherwise. O(1).

source
Base.length — Method.
length(heap) :: K

Returns the number of values currently stored inside the heap. O(1).

source
Base.pop! — Method.
pop!(heap) -> Pair(sval, trck)

Delete the stored value at top of the heap, and return the tracker => value.

The trck can then be used to re-insert it, or to insert another value.

The heap may need to be rebalanced, so O(log m).

See also: extract!, delete!

source
Base.setindex! — Method.
setindex!(heap, new_value, trck) -> heap

Begin tracking new_value using trck if such tracker is not yet in use, update the value pointed by trck if such tracker was already in use.

Will rebalance the heap if necessary. O(log m). Note: a vector with length equal to the highest used trck is kept, so giving new_value and arbitrarily large tracker can cause massive (and unnecessary) memory use.

See also: update!

source
TrackingHeaps.last_child_ix — Method.
last_child_ix

Internal helper method. Do not use. Subject to change.

source
TrackingHeaps.parent_ix — Method.
parent_ix

Internal helper method. Do not use. Subject to change.

source
TrackingHeaps.sift! — Method.
sift!(heap, ix, previous_sval)

Internal use. May be documented in the future. Avoid use unless strictly necessary.

source
TrackingHeaps.sift_down! — Method.
sift_down!(heap, ix)

Internal use. May be documented in the future. Avoid use unless strictly necessary.

source
TrackingHeaps.sift_up! — Method.
sift_up!(heap, ix)

Internal use. May be documented in the future. Avoid use unless strictly necessary.

source