openanalysis.base_data_structures module¶

class
openanalysis.base_data_structures.
UnionFind
¶ Unionfind data structure.
Each unionFind instance X maintains a family of disjoint sets of hashable objects, supporting the following two methods:
 X[item] returns a name for the set containing the given item. Each set is named by an arbitrarilychosen one of its members; as long as the set remains unchanged it will keep the same name. If the item is not yet part of a set in X, a new singleton set is created for it.
 X.union(item1, item2, …) merges the sets containing each item into a single larger set. If any item is not yet part of a set in X, it is added to X as one of the members of the merged set.

union
(*objects)¶ Find the sets containing the objects and merge them all.

class
openanalysis.base_data_structures.
PriorityQueue
¶ A simple Priority Queue Implementation for usage in algorithms. Internally uses heapq to maintain minheap and tasks are added as tuples (priority,task) to queue. To make the order of tasks with same priority clear, count of element insertion is added to the tuple, making it as (priority,count,task), which means that tasks are first ordered by priority then by count

add_task
(task, priority)¶ Add a task to priority queue
Parameters:  task – task to be added to queue
 priority – priority of the task, must be orderable

remove
(task)¶ Removes the tasks from Queue Currently it takes O(n) time to find , and O(log n) to remove, making it O(n) further improvements can be done
Parameters: task – task to removed from the Queue

remove_min
()¶ Removes the minimum element of heap
Returns: task with less priority

update_task
(task, new_priority)¶ Updates the priority of exsisting task in Queue Updation is implemented as deletion and insertion, takes O(n) time further improvements can be done
Parameters:  task – task to be updated
 new_priority – new value of priority
