Addressable Heap¶
The most classic addressable heap is the Fibonacci, so let us create one.
Creating an addressable heap¶
If not explicitly provided otherwise the heap will have float keys and int values.
>>> import jheaps
>>> fibo = jheaps.create_addressable_fibonacci_heap()
Inserting Elements¶
Now that we have a new heap we can start adding elements. When inserting an element in an addressable heap, you get back a handle which can later be used in order to perform operations on the element, such as decreasing the key (increasing the priority of the element) or deleting it from the heap.
>>> handle1 = fibo.insert(5.5, 1)
>>> handle2 = fibo.insert(100.5, 2)
>>> handle3 = fibo.insert(3.3, 3)
>>> handle4 = fibo.insert(52.3, 4)
>>> handle5 = fibo.insert(30.0, 5)
Element key-value¶
The key and the value can be read directly using properties
AddressableHeapHandle.key
and AddressableHeapHandle.value
from the handle.
>>> print('Key: {}'.format(handle1.key))
>>> print('Value: {}'.format(handle1.value))
Values can also directly be changed.
>>> handle1.value = 15
As keys can only be decreased, we provide a dedicated method for this,
AddressableHeapHandle.decrease_key()
.
>>> handle1.decrease_key(4.5)
Inspecting the size of the heap¶
The number of elements in the heap can be found using:
>>> print(len(fibo))
Method AddressableHeap.is_empty()
can be used to check if the heap is
empty.
>>> fibo.is_empty()
Finding the element with the minimum key¶
A handle to the element with the minimum key can be acquired using:
>>> handle6 = fibo.find_min()
Deleting the element with the minimum key¶
The element with the minimum key can be removed from the heap using:
>>> handle7 = fibo.delete_min()
The returned handle can only be used for accessing the properties
AddressableHeapHandle.key
and AddressableHeapHandle.value
.
Calling any other method on the handle will raise an exception.
Deleting elements¶
Searching in heaps is not possible, but elements can be deleted from corresponding handle. Thus, the user can use some external indexing mechanism in order to keep track of handles. Given a handle use
>>> handle4.delete()
to delete the element from the heap. Again after deletion you can only access the key and value from the handle, but all other methods raise exceptions.
Increasing the priority of an element¶
Sometimes we want to increase the priority of an element in the heap (recall how
Dijkstra’s algorithm works). This can be performed using the handle by calling
method AddressableHeapHandle.decrease_key()
.
>>> handle2.decrease_key(1.5)
Clearing the heap¶
All elements of the heap can be removed by using method AddressableHeap.clear()
.
>>> fibo.clear()