Python中的堆与优先级队列
Python中的堆与优先级队列
heapq模块
Python内置提供了一个堆队列的算法实现，也称优先级队列，在Python中可以将堆看做原生的list，heap[0]代表最小的元素, heap.sort()可以保持堆排序
方法介绍
heapq.heappush(heap, item) # 将item中的值加入heap中，并保持堆的不变性 heapq.heappop(heap) # 弹出堆中最小的元素，也可以heap[0],如果不存在数据则会抛出下标越界异常 heapq.heappushpop(heap, item) # 将item中的值加入heap中，并保持堆的不变性，然后弹出堆中最小的值 heapq.heapify(x) # 将列表X转化为堆，O(1)时间
实例
# 创建列表用于装载数据 stack = [] # 将列表转化为堆 heapq.heapify(stack) # 添加数据，并设置优先级，如果设置了优先级，则整个堆必须以优先级的形式存 heapq.heappush(stack, (2, "2222")) heapq.heappush(stack, (3, "33333")) heapq.heappush(stack, (1, "11111")) # 因为heapq 实现的是小顶堆, 所以默认弹出最小的, 如果没有数据抛出IndexError异常 print(heapq.heappop(stack)) # 也可以直接通过下标的形式 print(stack[0]) # 查看列表内部排序情况 print(stack) # 将数据存入，并弹出最小值 print(heapq.heappushpop(stack, (4,"4444")))
# out (1, 11111) (2, 2222) [(2, 2222), (3, 33333)] (2, 2222)
