使用ptyhon实现堆

"""
堆的相关操作：
1，从最后到头逐个调整元素
2，取出堆定的那个需要的元素
3，将最后一个元素放到堆顶，然后逐个交换完成堆的调整
4，插入元素时，直接插入末尾，然后调整真个堆
这里以最小堆为例子，其实就是优先队列
"""


class Heap:
    def __init__(self, data):
        self.data = data
        self.length = len(data)
        self.init_heap()

    # 初始化调整个堆的结构
    def init_heap(self):
        # 从最后一个元素开始调整
        for i in range(self.length-1, -1, -1):
            # 找到他的根节点
            if i % 2 == 0:
                root_index = i//2-1
            else:
                root_index = i//2

            if root_index >= 0:
                # print('找到根节点：', root_index)
                # print(i, root_index)

                if self.data[root_index] > self.data[i]:      # 不符合顶堆的定义就交换
                    self.data[root_index], self.data[i] = self.data[i], self.data[root_index]
                    self.deal_all_sons(i)    # 一旦发生交换，就可能会让该堆不符合堆的定义
        return

    def deal_all_sons(self, i):
        # 从堆顶往堆左右两端的元素调整
        # 左节点
        left_index = i*2+1
        # 右节点
        right_index = (i+1) * 2

        # 子堆定点和左节点相比较
        if left_index <= self.length-1 and self.data[i] > self.data[left_index]:
            self.data[i], self.data[left_index] = self.data[left_index], self.data[i]
            self.deal_all_sons(left_index)     # 递归调整所有的节点

        # 子堆定点和右节点相比较
        if right_index <= self.length - 1 and self.data[i] > self.data[right_index]:
            self.data[i], self.data[right_index] = self.data[right_index], self.data[i]
            self.deal_all_sons(right_index)    # 递归调整所有的节点

    # 取出堆顶的一个元素
    def get_one(self):
        if self.length < 1:
            print('序列的长度不足！')

        ret = self.data[0]
        # 将堆尾的那个元素放到堆顶
        self.data[0] = self.data[self.length-1]
        # 删除堆尾的位置
        del self.data[self.length-1]
        self.length -= 1
        # 调整整个堆
        self.deal_all_sons(0)

        return ret

    # 向堆中插入一个元素
    def insert(self, x):
        self.data.append(x)
        self.length += 1
        self.init_heap()  # 重新调整整个堆


def main():
    n = 10
    # list_data = [0] * n
    list_data = [66, 5, 52, 12, 51, 53, 26, 70, 92, 85]

    # for i in range(n):
    #     list_data[i] = rd.randint(1, 100)

    print('获得的初始数据：', list_data)

    heap = Heap(list_data[0:])  # 最好拷贝进去处理，不然万一在外面改了这个数组，堆就可能挂掉
    print('初始化之后的数据：', heap.data)

    # 取出堆顶的元素
    print('取出的元素：', heap.get_one())
    print(heap.data)

    # 插入元素
    heap.insert(31)
    print('插入元素{}之后：'.format(31), heap.data)

    return


if __name__ == '__main__':
    # print(1//2)
    main()