在Python中使用什么数据结构实现堆

Question

我在为Udacity课程编写一个自定义的堆实现，想要一个堆能够通过元素的堆索引和键值返回一个指标值。

最后，我做了一个包含元组 (指标, 键)的堆列表。

但是为了通过键值获取正确的元素，我不得不创建一个单独的映射，并在堆每次变化时保持它的有效性。

所以最后，我不得不把所有函数的参数从两个改为三个，比如从heapup(heap, i)变成heapup(heap, i, map)。

我在想，是否有更简单的方法来通过过程、列表和字典来实现这个功能，还是说需要一个堆对象来把映射隐藏起来呢？

 def heapup(L, i, map):

    if i == 0: return i # we reached the top!
    if i >= len(L): return i
    if L[parent(i)] > L[i]:
       # print "going up"
        (L[i], L[parent(i)]) = (L[parent(i)], L[i])
        map[L[i][1]] = i
        map[L[parent(i)][1]] = parent(i)
        return up_heapify(L, parent(i), map)
    else:
     #   print "going down"
        if leaf(L,i): return i
        if one_child(L,i): return i # we could only come this way
        if L[i] > L[left(i)]: # compare with left child
            (L[i], L[left(i)]) = (L[left(i)], L[i])
            map[L[i][1]] = i
            map[L[left(i)][1]] = left(i)
            return left(i)
        if L[i] > L[right(i)]: # compare with right child
            (L[i], L[right(i)]) = (L[right(i)], L[i])
            map[L[i][1]] = i
            map[L[right(i)][1]] = right(i)
            return right(i)

我希望在这个函数中去掉映射，但仍然能够通过键值从堆中获取元素的值，现在我可以这样做：

item = heap[map[key]]

例如：

如果

L = [(3,'A'), (5, 'D'), (4, 'G') ...] 

那么

map = {'A':0, 'D':1, 'G': 2, ...} 

这样我就可以得到一个元素的值：

L[map['G']] 

这将给我4

Answer 1

使用 heapq 模块，详细信息可以查看这个链接：http://docs.python.org/2/library/heapq.html。

这个模块实现了一种叫做堆队列的算法，通常也被称为优先队列算法。