I'm working on an A* search algorithm implemention and this is what I came up with for the open list:
from heapq import heappush, heappop class OpenList(set): ''' This uses a heap for fast retrieval of the node with the lowest path score. It also uses a set for efficiently checking if a node is contained. ''' REMOVED = object() def __init__(self, *args, **kwargs): set.__init__(self, *args, **kwargs) self._heap =  def add(self, node): set.add(self, node) heappush(self._heap, (node.get_path_score(), node)) def remove(self, node): set.remove(self, node) i = self._heap.index((node.get_path_score(), node)) self._heap[i] = self.REMOVED def pop_node_with_lowest_path_score(self): ''' remove and return the node with the lowest path score ''' item = heappop(self._heap) while item is self.REMOVED: item = heappop(self._heap) set.remove(self, item) return item
Should I keep the path_score in the heap, when I mark the item as removed as in the following code:
self._heap[i] = (node.get_path_score(), self.REMOVED)
What do you think about it? What can be made more efficient, simple or cleaner?