Return to Answer

1. Instead of calling update_pos at the end of a heap operation, update it as you go along. For example, percUp becomes:

    cur_pos = len(self.list) - 1
    parent_pos = cur_pos // 2
    while parent_pos:
    cur = self.list[cur_pos]
    parent = self.list[parent_pos]
    if self.G[parent][2] > self.G[cur][2]:
    self.list[parent_pos] = cur
    self.pos[cur] = parent_pos
    self.list[cur_pos] = parent
    self.pos[parent] = cur_pos
    cur_pos = parent_pos
    parent_pos //= 2
   

And similarly for percDown.

1. Having written that, a simpler approach to deletion from a heap is simply to leave the object in the heap but mark it somehow as deleted. Then when you extract the minimum you check to see if it was marked as deleted, and if it was, you throw it away and extract another one.

2. If you use the "mark object as deleted" method, then you would be able to use Python's built-in heapq module (see in particular the "Priority Queue Implementation Notes"). See this answer for an example implementation.

3. It looks (from the name "G" for the scores) as though you are using this to implement the priority queue of unvisited nodes in the A* search algorithm. But then it is not clear why you need to delete items from the middle of the heap—in the A* algorithm this never happens (an item is only deleted when it is popped as the minimum item). So you could just not implement deletion, and since the pos dictionary is only used by the deletion method, you wouldn't have to maintain it, and so you could just use Python's built-in heaps directly. See this answer for an example.

1. Instead of calling update_pos at the end of a heap operation, update it as you go along. For example, percUp becomes:

    cur_pos = len(self.list) - 1
    parent_pos = cur_pos // 2
    while parent_pos:
    cur = self.list[cur_pos]
    parent = self.list[parent_pos]
    if self.G[parent][2] > self.G[cur][2]:
    self.list[parent_pos] = cur
    self.pos[cur] = parent_pos
    self.list[cur_pos] = parent
    self.pos[parent] = cur_pos
    cur_pos = parent_pos
    parent_pos //= 2
   

And similarly for percDown.

1. Having written that, a simpler approach to deletion from a heap is simply to leave the object in the heap but mark it somehow as deleted. Then when you extract the minimum you check to see if it was marked as deleted, and if it was, you throw it away and extract another one.

2. If you use the "mark object as deleted" method, then you would be able to use Python's built-in heapq module (see in particular the "Priority Queue Implementation Notes"). See this answer for an example implementation.

3. It looks (from the name "G" for the scores) as though you are using this to implement the priority queue of unvisited nodes in the A* search algorithm. But then it is not clear why you need to delete items from the middle of the heap—in the A* algorithm this never happens (an item is only deleted when it is popped as the minimum item). So you could just not implement deletion, and since the pos dictionary is only used by the deletion method, you wouldn't have to maintain it, and so you could just use Python's built-in heaps directly. See this answer for an example.