I'm implementing A* (A star) algorithm in Python.
As you know we have have "open set" which consists a list of nodes we plan to explore.
In the algorithm we get the node with lowest F(n) value (estimated total cost) from open set.
We often use PriorityQueue, but for some reason which I don't understand why PriorityQueue doens't get the node with lowest value.
So rather I made an array list (regular list in Python) named "frontier" and keep the "open set" there.
There are two ways to use that like PriorityQueue.
currentNode = min(frontier)
to get the minimum value from the open set.
Or we can sort the array everytime we add new node into it, and just use "pop" to get the lowest value.
#adding a node
frontier.append(someNode)
sorted(frontier)
#taking out the node
currentNode = frontier.pop(0)
Which one is faster?
Using min() or first sorting and then using pop() ?
What algorithm does "min()" in Python use to get the minimum value from an array?
There are three operations that this data structure s needs to perform, these are
F(n)The easiest way to implement would be to have a plain list and use min(s) to get the min value or min(range(len(values)), key=s.__getitem__) to get the index.
This runs in O(n) because it looks at every element once. Adding an element to the end of the list runs in O(1) and removing from an arbitrary index runs in O(n) because all successive elements need to be shifted.
The idea to sort the array every time is slightly worse, as sorting runs in O(n log n). You save some time by sorting the min element to the end of the list, where it can be removed in O(1), but in total it will be slower.
The best solution is to have a heap or priority queue. It maintains the min element at the top where it can be retrieved in O(1) and allows inserting and removing elements in O(log n).