Efficient bookkeeping in heap

Question

I'm trying to implement a heap using list data structure. I'd also like to keep track of the position of elements in the list in order to enable easy deletion. My implementation involves looping through the entire list to update the positions after an insert/delete combo. I'm afraid this raises the time complexity from O(log n) to O(n). Is there a better way of keeping track of elements' position? Currently, update method is what takes care of the bookkeeping.

class heap():
 ''' Min-Heap'''
 def __init__(self,G):
 self.list=[0] #to ease dealing with indices, an arbitrary value at index 0
 self.pos={} #holds position of elements with respect to list
 self.G = G #Graph, contains the score for each element in G[element][2]
def update_pos(self):
 self.pos = {}
 for i in xrange(1,len(self.list)):
 self.pos[self.list[i]]=i
def percUp(self): #percolate up, called by insert method
 start = len(self.list)-1
 while start//2>0:
 if self.G[self.list[start/2]][2] > self.G[self.list[start]][2]:
 self.list[start/2],self.list[start] = self.list[start],self.list[start/2]
 start = start//2
def insert(self,element):
 self.list.append(element)
 self.percUp()
 self.update_pos()
def percDown(self,start=1): #percolate down, called by extract_min method
 while 2*start < len(self.list):
 min_ind = self.getMinInd(start)
 if self.G[self.list[start]][2] > self.G[self.list[min_ind]][2]:
 self.list[start],self.list[min_ind] = self.list[min_ind],self.list[start]
 start = min_ind
def extract_min(self):
 self.list[-1],self.list[1] = self.list[1],self.list[-1]
 small = self.list[-1]
 self.list = self.list[:-1]
 self.percDown()
 self.update_pos()
 return small
def delete(self,pos):
 self.list[-1],self.list[pos] = self.list[pos],self.list[-1]
 self.pos.pop(self.list[pos])
 self.list = self.list[:-1]
 self.percDown(pos)
 self.update_pos()
def getMinInd(self,start):
 if 2*start+1 > len(self.list)-1:
 return 2*start
 else:
 if self.G[self.list[2*start]][2]<self.G[self.list[2*start+1]][2]:
 return 2*start
 else:
 return 2*start+1

Answer 1

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.

2. 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.

3. 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.

4. 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.