python heapq 模块

堆的概念

堆是用数组表示的二叉树，分为大根堆和小根堆：大根堆是堆顶元素最大的堆，小根堆是堆顶元素最小的堆

 堆的建立

堆用列表来表示。在往堆中加入元素时，在列表最后加入一个元素并与其父节点比较（n/2位置）看是否需要进行交换，然后层层比较直到根节点

python heapq

# 建立小根堆
        import heapq
        a = list()
        heapq.heappush(a, 18)
        heapq.heappush(a, 1)
        heapq.heappush(a, 20)
        heapq.heappush(a, 10)
        heapq.heappush(a, 5)
        heapq.heappush(a, 200)
        print(a)  #  [1, 5, 20, 18, 10, 200]

# 建立大根堆 - heapq默认建立的是小根堆，将数据取反建立小根堆，其实就是相当于原数据的大根堆（记得输出的时候也要取反）
        b = list()
        for i in a:
            heapq.heappush(b, -i)
        print(list(map(lambda x: -x, b)))

# 直接将列表转化成小根堆
        c = [18, 1, 20, 10, 5, 200]
        heapq.heapify(c)
        print(c)
# 直接将列表转化为大根堆
        c = [-i for i in c]
        heapq.heapify(c)
        c = [-i for i in c]
        print(c)

# heappop从堆中弹出并返回最小的值
        for i in range(len(a)):
            print(heapq.heappop(a))