1

我正在为课程编写一个自定义堆实现，Udacity并且需要一个通过堆索引和元素键返回元素度量值的堆。

我最终得到了一个包含tuples (Metric, Key).

但是为了通过键获得正确的元素，我必须创建一个单独的映射并保持它对堆中每次更改的有效性。

heapup(heap, i)所以最后，我不得不将 map 传递给所有函数，而不是使用带有两个参数的函数 - heapup(heap, i, map)。

我想知道是否有更简单的方法可以通过程序、列表和字典来做到这一点。还是需要 Heap 对象将 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

4

1 回答 1

3

使用 heapq http://docs.python.org/2/library/heapq.html和描述：

“这个模块提供了堆队列算法的实现，也称为优先队列算法。”

于 2013-05-06T17:56:43.113 回答