It is Python package of an indexed binary heap, that designed to solve the inefficiencies of Python heapq package.
In many of the heap-based algorithms, like Prim's Algorithm to find Minimum Spanning Tree (MST), or Dijkstra Algorithm to find shortest path in a positively weighted graph, we need the ability to modify the value of elements within a heap, while maintaining the heap order in O(logN) time complexity.
In Python's most popular heap package, heapq, such operations are not allowed. So we cannot implement heap-based algorithms that require value changes efficiently using heapq.
Here I develop my own solution using an Indexed Heap idea. I use additional dictionaries to index elements inside a heap, and grarantee a O(logN) time complexity when modifying elements inside a heap.
Please check Indexed_Heap/Indexed_Heap.py file. It contains doumented Python code and unit tests.
The code is tested under Python 2.7. It does not have any dependencies.
Prepare the input. Suppose we have a test_obj class that serves as the elements inside the indexed heap. We create test_obj lists as input array:
class test_obj(object):
def __init__(self, id, val):
self.id = id
self.val = val
def __lt__(self, other):
return self.val < other.val
test_arr = []
input_dict = {'a': 55, 'b': 65, 'c': 20, 'd': 90, 'e': 42, 'f': 72, 'g': 3}
for k,v in input_dict.items():
test_arr.append(test_obj(k, v))
Intialize the indexed heap and heapify it:
hp = Indexed_Heap(test_arr)
hp.heapify()
The current smallest element has value 3:
print(hp.peek().val) # output 3
After we change the element, the smallest element is the one with value 20:
hp.change_value(test_obj('g', 50))
print(hp.peek().val) # output 20