数据结构学习-python实现-优先队列--0417

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