PriorityQueue.py 文件源码

def __down_heap(self, i):
        """
        Rebalances the heap (by moving small values down)
        """
        # Calculate left and right child indices
        l = 2*i+1
        r = 2*i+2
        # Find index of the greatest of these elements
        if l < self.size and self.pq_array[l,0] > self.pq_array[i,0]:
            greatest = l
        else:
            greatest = i
        if r < self.size and self.pq_array[r,0] > self.pq_array[greatest,0]:
            greatest = r
        # Continue rebalancing if necessary
        if greatest != i:
            # swap elements at indices i, greatest
            self.pq_array[i], self.pq_array[greatest] = np.copy(self.pq_array[greatest]), np.copy(self.pq_array[i])
            # Update hash tables
            self.exp_hash[self.pq_array[i,1]], self.exp_hash[self.pq_array[greatest,1]], self.pq_hash[i], self.pq_hash[greatest] = i, greatest, self.pq_array[i,1], self.pq_array[greatest,1]

            self.__down_heap(greatest)