もちろん、カスタム ヒープの実装を作成していUdacityましたが、要素のヒープ インデックスとキーの両方を介して要素のメトリック値を返すヒープが必要でした。
を含むヒープのリストになりましたtuples (Metric, Key)。
しかし、キーを介して適切な要素を取得するには、別のマップを作成し、ヒープ内の変更ごとにその有効性を維持する必要がありました。
そのため、最終的に、 のような 2 つのパラメーターを持つ関数を使用する代わりに、heapup(heap, i)すべての関数に map を渡す必要がありました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を与えるでしょう