class PriorityQueue:
def __init__(self):
self.heap_array = [(0, 0)]
self.current_size = 0
def build_heap(self, alist):
self.current_size = len(alist)
self.heap_array = [(0, 0)]
for x in alist:
self.heap_array.append(x)
i = len(alist) // 2
while i > 0:
self.perc_down(i)
i -= 1
def perc_down(self, i): # 较大子节点下沉
while i * 2 <= self.current_size:
mc = self.minchild(i)
if self.heap_array[i][0] > self.heap_array[mc][0]:
self.heap_array[i], self.heap_array[mc] = self.heap_array[mc], self.heap_array[i]
i = mc
def minchild(self, i):
if i * 2 > self.current_size:
return -1
else:
if i * 2 + 1 > self.current_size:
return i * 2
else:
return i * 2 + 1
def perc_up(self, i): # 较小节点上浮
while i // 2 > 0:
if self.heap_array[i][0] < self.heap_array[i//2][0]:
self.heap_array[i//2], self.heap_array[i] = self.heap_array[i], self.heap_array[i//2]
i //= 2
def add(self, k):
self.heap_array.append(k)
self.current_size += 1
self.perc_up(self.current_size)
def del_min(self):
retval = self.heap_array[1][1]
self.heap_array[1] = self.heap_array[self.current_size]
self.current_size -= 1
self.heap_array.pop()
self.perc_down(1)
return retval
def is_empty(self):
if self.current_size == 0:
return True
else:
return False
def decrease_key(self, val, amt):
done = False
i = 1
my_key = 0
while not done and i <= self.current_size:
if self.heap_array[i][1] == val:
done = True
my_key = i
else:
i += 1
if my_key > 0:
self.heap_array[my_key] = (amt, self.heap_array[my_key][1])
self.perc_up(my_key)
def __contains__(self, vtx):
for pair in self.heap_array:
if pair[1] == vtx:
return True
return False
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。