pythonheapq优先级队列堆

http://docs.python.org/2/library/heapq.html

heapq 是一个小堆(当然也可以通过变换优先级的值 变成大堆)

heapq 可以 压入 普通的整数 也可以 压入list 这样就能 优先级 附带其它属性了

heapq 本身 支持 push 和 pop 操作

但是如何 调整已经加入的元素的优先级值呢?

比如 将某个元素的优先级 调小, 使其向堆顶移动, 这里需要知道这个元素当前在堆的哪个位置,接着 执行 堆调整的交换操作,调整这个元素的位置

首先如何查找到元素的位置,这个就比较头痛,没想到办法让heapq在调整优先级的过程中同时记录元素的位置,如果不能这样快速的查找位置,那heapq就没有意义了

因此只能采用另外一种方式,类似于线性探测解决冲突的hash表所做的,将删除的元素 标记 ID 为-1 ,认为其被删除了, 在出队操作中, 对于已经被删除的元素则忽略, 接着将调整优先级的 新元素重新插入到队列里面去

但是存在一个问题, 这样不能通过简单的查看队列长度来判定队列是否为空, 需要封装一个pop操作来抛出异常, 同时在调用pop的时候 注意 捕获异常

原文地址:https://www.cnblogs.com/liyonghelpme/p/4273769.html