哟,有实用价值
可以看到,加入是随机的,而吐出是顺序的。
# coding = utf-8 # 使用二叉堆实现的优先队列(列表) class BinaryHeap: def __init__(self): self.heap_list = [0] self.current_size = 0 def perc_up(self, i): while i // 2 > 0: if self.heap_list[i] < self.heap_list[i//2]: self.heap_list[i//2], self.heap_list[i] = \ self.heap_list[i], self.heap_list[i//2] i //= 2 def insert(self, k): self.heap_list.append(k) self.current_size = self.current_size + 1 self.perc_up(self.current_size) def min_child(self, i): if i * 2 + 1 > self.current_size: return i * 2 else: if self.heap_list[i*2] < self.heap_list[i*2+1]: return i * 2 else: return i * 2 + 1 def perc_down(self, i): while (i*2) <= self.current_size: mc = self.min_child(i) if self.heap_list[i] > self.heap_list[mc]: self.heap_list[i], self.heap_list[mc] = \ self.heap_list[mc], self.heap_list[i] i = mc def del_min(self): ret_val = self.heap_list[1] self.heap_list[1] = self.heap_list[self.current_size] self.current_size = self.current_size - 1 self.heap_list.pop() self.perc_down(1) return ret_val def build_heap(self, a_list): i = len(a_list) // 2 self.current_size = len(a_list) self.heap_list = [0] + a_list[:] while i > 0: self.perc_down(i) i -= 1 bh = BinaryHeap() bh.build_heap([9, 5, 6, 2, 3]) print(bh.del_min()) print(bh.del_min()) print(bh.del_min()) print(bh.del_min()) print(bh.del_min())
2 3 5 6 9