Efficient implementation of priority queue

Question

I am trying to solve a maze problem.

The input data is a matrix, where the individual element represents the height of the mountain in that particular area, I have to start from position (0,0) and go to the position (n-1, n-1); where n is the size of the maze, my goal is to return the minimum number of possible climb round that I have to make in order to achieve this goal.

For example:

b = 010
 010
 010

In the matrix b,If I start from (0,0) I have to climb to height 1, now I am on the hill and I have to go down, so the total number of climb round is

abs(0(height of starting position) - 1(height of mountain)) + abs(1(height of mountain) - 0(height of the third column)) = 2

If I reach to third column then I do nnot have to climb any further round as my goal (2,2) would be at same level

c = 010
 101
 010

Similarly for c, the answer would be 4

A typical example would be

75218176
00125954
30062751
01192976
24660156
14932066
44532310
60429682

"""
self.location stores the location of current node
self.cost stores the cost or path length from adjacent node approaching from a particular path, for example in the above example If I have coming along the path 752
 then cost of the node whose location is (0,2) would be 3, as the difference of height 5 and height 2 is 3
self.altitude simply stores the number which is at the location
self.totalCost represent the totalCost from the begenning, for example: for the path 752, the total cost of '2' would be 7- 5 + 5 -2 = 5
getTotalcost() simply add the parent cost with the difference in altitude of parent and self
neighbours() returns the possible node which can be reached from the current position.
Open is basically implementation of priority queue, I have not used heapq because in order to maintain the invariancy in structure I am not supposed to delete any element at random, although I can re-heapify after deletion but that seems to an obvious choice for inefficiency
"""
class node:
 def __init__(self, loc):
 self.location = loc
 self.cost = 0
 self.altitude = 0
 self.parent = None
 self.totalCost = 0 
 def __eq__(self, other):
 return self.location == other.location
 def __hash__(self):
 return hash(self.location)
 def getTotalcost(self):
 if self.parent:
 self.totalCost = self.cost + self.parent.totalCost
 return self.totalCost
 def __lt__(self, other):
 return self.getTotalcost() < other.getTotalcost()
def neighbours(S, Node):
 a,b = Node.location
 options = []
 for i in (a, b + 1), (a, b - 1), (a + 1, b), (a - 1, b):
 if min(i) >= 0 and max(i) < S:
 options.append(node(i))
 return options
class Open:
 def __init__(self, point):
 self.container = [point]
 self.se = set(self.container)
 self.l = 1
 def push(self, other):
 if not(other in self.se):
 self.properPlace(other)
 else:
 a = other
 b = self.container.index(other)
 k = self.container[b]
 if k.getTotalcost() > a.getTotalcost():
 del self.container[b]
 self.l -= 1
 self.se.remove(k)
 self.properPlace(other)
 def __iter__(self):
 return iter(self.container)
 def rem(self):
 self.l -= 1
 return self.container.pop(0)
 def properPlace(self, other):
 i = 0
 while i < self.l and self.container[i].getTotalcost() < other.getTotalcost():
 i += 1
 self.container.insert(i, other)
 self.l += 1
 self.se.add(other)
def path_finder(maze):
 maze= maze.split("\n")
 l = len(maze)
 start = node((0,0))
 start.altitude = int(maze[0][0])
 start.totalCost = 0
 r = Open(start)
 visited = set()
 while True:
 i = r.rem()
 if i.location == (l - 1, l- 1):
 return i.getTotalcost()
 for j in neighbours(l, i):
 j.altitude = int(maze[j.location[0]][j.location[1]])
 if j not in visited:
 j.cost = abs(i.altitude - j.altitude)
 j.parent = i
 r.push(j)
 visited.add(i)

I have some thoughts that my implementation of priority queue is inefficient, am I right? If yes, then how can I make it more efficient? How can I make the program efficient?

• scnerd: Do you need to implement the priority queue yourself (for homework, just for the fun/challenge, etc.), or would a pre-built solution be just as good?
• xrfxlp: It would be best if someone helps me to find the chunk and suggest to improve where the maximum computational time goes in my code, else even the more efficient implementation would be good too.

Answer 1

The advice I think most important:

• stick to the Style Guide for Python Code
  It helps everyone - including yourself - read your code.

• Naming: name things for what they can/will be used for, their raison d'être.
  For example, the class featuring push(), rem(), and _properPlace() is not used to be open or open something. It looks a priority queue with increase_priority().
  The instance r in path_finder() holds a set of tentative costs, or, if you insist, "open" nodes.
  The usual suggestion in the context of path finding is to use a Fibonacci_heap - there is PyPI fibheap.

• Modelling
  node is a strange hybrid of node and edge, given its single parent and cost:
  cost is not an attribute of a node, but an attribute of an edge, a pair of nodes

I suspect del and insert on Open.container to be the performance culprits.
You could try and adapt heapq:
locate nodes using index() as presented (O(n))
update cost and use _siftdown() to restore heap property