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)
评论列表
文章目录