Heap Factories¶
Creating heaps can be accomplished using factory methods. Heaps are based on two main
categories depending on whether they are addressable or not. Addressable heaps follow the
AddressableHeap interface and support the addition of key-value pairs
while classic heaps use the Heap interface and support only keys.
Both keys and values (when applicable) can have different types. Native support and therefore better performance is provided for float and int keys or values. All other types are represented using object and thus entail additional overhead. When keys are objects, comparisons are performed using __lt__ and __eq__. Note that float and int are translated to double and long long in the backend which means that they do not use arbitrary precision arithmetic. Use object in order to handle arbitrary keys and values.
Additionally several addressable heaps are also mergeable heaps following the
Mergeable interface and thus efficiently support melding with another heap. Note, however,
that after a meld one of the two heaps becomes unusable. Finally, performing cascading melds
although efficient due to the use of union-find with path compression, invalidates the claimed bounds.
AddressableHeaps¶
Depending on the given parameters different types of heaps can be represented. All heaps
returned by the following functions are instances of AddressableHeap.
-
jheaps.create_addressable_dary_heap(key_type=<class 'float'>, value_type=<class 'int'>, d=4, explicit=False)[source]¶ Create an addressable d-ary heap.
- Parameters
key_type (float, int or object) – the key type
value_type (float, int or object) – the value type
d (int) – the degree of the d-ary heap
explicit (boolean) – if True the heap is an actual tree, otherwise is it stored as an array
- Returns
the heap
- Return type
-
jheaps.create_addressable_binary_heap(key_type=<class 'float'>, value_type=<class 'int'>, explicit=False)[source]¶ Create an addressable binary heap.
- Parameters
key_type (float, int or object) – the key type
value_type (float, int or object) – the value type
explicit (boolean) – if True the heap is an actual tree, otherwise is it stored as an array
- Returns
the heap
- Return type
-
jheaps.create_addressable_fibonacci_heap(key_type=<class 'float'>, value_type=<class 'int'>, simple=False)[source]¶ Create an addressable Fibonacci heap.
- Parameters
key_type (float, int or object) – the key type
value_type (float, int or object) – the value type
simple (boolean) – if true then the simple variant is returned, otherwise the classic
- Returns
the heap
- Return type
-
jheaps.create_addressable_pairing_heap(key_type=<class 'float'>, value_type=<class 'int'>, type=None)[source]¶ Create an addressable pairing heap. Different pairing heap variants can be constructed using the parameter type.
- Parameters
key_type (float, int or object) – the key type
value_type (float, int or object) – the value type
type (None, 'rank' or 'costless_meld') – the type of pairing heap to create
- Returns
the heap
- Return type
-
jheaps.create_addressable_hollow_heap(key_type=<class 'float'>, value_type=<class 'int'>)[source]¶ Create an addressable hollow heap.
- Parameters
key_type (float, int or object) – the key type
value_type (float, int or object) – the value type
- Returns
the heap
- Return type
-
jheaps.create_addressable_radix_heap(key_type=<class 'float'>, value_type=<class 'int'>, min=None, max=None)[source]¶ Create an addressable radix heap. Radix heaps are monotone heaps stored using buckets. The key type can only be float or int. The number of buckets depends on the difference between the min and max values provided.
- Parameters
key_type (float or int) – the key type
value_type (float, int or object) – the value type
min (float or int depending on key_type) – minimum key value
max (float or int depending on key_type) – maximum key value
- Returns
the heap
- Return type
Heaps¶
Depending on the given parameters different types of heaps can be represented. All heaps
returned by the following functions are instances of Heap.
-
jheaps.create_implicit_dary_heap(key_type=<class 'float'>, d=4)[source]¶ Create an implicit (array-based) d-ary heap.
- Parameters
key_type (float, int or object) – the key type
d (int) – the degree of the d-ary heap
- Returns
the heap
- Return type
-
jheaps.create_implicit_weak_binary_heap(key_type=<class 'float'>, bulk_insert=False)[source]¶ Create an implicit (array-based) weak binary heap.
- Parameters
key_type (float, int or object) – the key type
bulk_insert (boolean) – whether to use the variant which supports bulk insertion
- Returns
the heap
- Return type
-
jheaps.create_implicit_binary_heap(key_type=<class 'float'>)[source]¶ Create an implicit (array-based) binary heap.
- Parameters
key_type (float, int or object) – the key type
- Returns
the heap
- Return type
-
jheaps.create_radix_heap(key_type=<class 'float'>, min=None, max=None)[source]¶ Create a radix heap. Radix heaps are monotone heaps stored using buckets. The key type can only be float or int. The number of buckets depends on the difference between the min and max values provided.
- Parameters
key_type (float or int) – the key type
value_type (float, int or object) – the value type
min (float or int depending on key_type) – minimum key value
max (float or int depending on key_type) – maximum key value
- Returns
the heap
- Return type