[数据结构][Python]实现二叉堆

深碍√TFBOYSˉ_ 2022-01-22 10:39 252阅读 0赞

class BinaryHeap(object):
        def __init__(self):
            self.item_list = [0]
    
        def insert(self,new_item):
            self.item_list.append(new_item)
            self.item_list[0]+=1
            self.upward_adjust(self.item_list[0])
    
        def upward_adjust(self,index):
            while index//2>0:
                if self.item_list[index]<self.item_list[index//2]:
                    temp = self.item_list[index]
                    self.item_list[index]=self.item_list[index//2]
                    self.item_list[index//2]=temp
                    index = index//2
                else:
                    break
    
        def get_min(self):
            if self.item_list[0]>0:
                return self.item_list[1]
            else:
                return None
    
        def pop_min(self):
            if self.item_list[0]==0:return None
            else:
                top_min = self.item_list[1]
                self.item_list[1]=self.item_list[self.item_list[0]]
                self.item_list[0]-=1
                self.downward_adjust(1)
                return top_min
    
        def downward_adjust(self, index):
            while 2 * index <= self.item_list[0]:  # 子节点存在
                if 2 * index + 1 <= self.item_list[0]:  # 左右子节点都存在
                    if self.item_list[2 * index] < self.item_list[2 * index + 1]:  # 左子节点更小
                        if self.item_list[index] > self.item_list[2 * index]:  # 比左子节点更大，交换
                            temp = self.item_list[index]
                            self.item_list[index] = self.item_list[2 * index]
                            self.item_list[2 * index] = temp
                            index = 2 * index  # 继续调整
                        else:  # 没有比子节点更大，停止调整
                            break
                    else:  # 右子节点更小
                        if self.item_list[index] > self.item_list[2 * index + 1]:  # 比右子节点更大，交换
                            temp = self.item_list[index]
                            self.item_list[index] = self.item_list[2 * index + 1]
                            self.item_list[2 * index + 1] = temp
                            index = 2 * index + 1  # 继续调整
                        else:  # 没有比子节点更大，停止调整
                            break
                else:  # 只存在左节点
                    if self.item_list[index] > self.item_list[2 * index]:  # 比左子节点更大，交换
                        temp = self.item_list[index]
                        self.item_list[index] = self.item_list[2 * index]
                        self.item_list[2 * index] = temp
                    else:  # 没有比子节点更大，停止调整
                        break
    
        def isEmpty(self):
            return 0 == self.item_list[0]
    
        # 返回堆中的项数
        def size(self):
            return self.item_list[0]
    
        # 从列表构建一个新的堆。覆盖掉当前的堆
        def build_heap(self, input_list):
            self.item_list = [0] + input_list
            self.item_list[0] = len(input_list)
            for index in range(self.item_list[0] // 2, 0, -1):  # 从最后一个有叶节点的元素起逐个向下调整
                self.downward_adjust(index)
    
    
    def main():
        bh = BinaryHeap()
        bh.build_heap([9, 5, 6, 2, 3, 10, 4, 1, 8, 7, 0])
    
        for i in range(11):
            print(bh.pop_min())
    
    
    if __name__ == "__main__":
        main()