相关疑难解决方法(0)

Dijkstra的算法教给我如下

while pqueue is not empty:
    distance, node = pqueue.delete_min()
    if node has been visited:
        continue
    else:
        mark node as visited
    if node == target:
        break
    for each neighbor of node:
         pqueue.insert(distance + distance_to_neighbor, neighbor)

但是我一直在阅读关于算法的一些阅读,我看到的很多版本都使用了reduce-key而不是insert.

为什么会这样,这两种方法之间有什么区别？

Python具有heapq实现堆数据结构的模块,它支持一些基本操作(push,pop).

如何从O(log n)中的堆中删除第i个元素？是否可以使用heapq或者我必须使用其他模块？

请注意,文档底部有一个示例:http: //docs.python.org/library/heapq.html ,它提出了一种可能的方法 - 这不是我想要的.我想要删除元素,而不仅仅是标记为删除.

使用最小/最大堆算法时,优先级可能会发生变化.处理此问题的一种方法是删除并插入元素以更新队列顺序.

对于使用数组实现的优先级队列,这可能是一个似乎可以避免的性能瓶颈,特别是对于优先级变化较小的情况.

即使这不是优先级队列的标准操作,这也是一个可以根据我的需要进行修改的自定义实现.

是否有众所周知的最佳实践方法来更新min/max-heap中的元素？

背景信息:我不是二叉树专家,我继承了一些代码,这些代码在优先级队列中重新插入了元素.我为重新排序新元素的min-heap做了一个重新插入函数 - 这给了一个可测量的改进(删除和插入),但这似乎是其他人可能已经解决的更优雅的问题办法.

我可以链接到代码,如果它有所帮助,但宁愿不太关注实现细节 - 因为这个Q&A可能保持一般.

如果我有一个heapq,其中包含一些元素,如:

import heapq


class Element(object):
    def __init__(self, name, val):
        self.name = name
        self.val = val

if __name__ == "__main__":
    heap = []
    e1 = Element('A', 1)
    e2 = Element('B', 65)
    e3 = Element('C', 53)
    e4 = Element('D', 67)
    ...

    heapq.heappush(heap, e1)
    heapq.heappush(heap, e2)
    heapq.heappush(heap, e3)
    heapq.heappush(heap, e4)
    ...

    #IF I want to take elements from the heap and print them I will call:
    while heap:
        new_e = heapq.heappop(heap)
        print new_e.name + ' ' + str(new_e.val)

假设我在堆上有50个元素.我想将元素e3的值从val = 53更改为val = 0.所以这不是堆的顶部元素.我也不想从堆中删除其他元素.我该怎么做这样的更新？