我寫Dijkstra算法的代碼，我們都應該找到從當前正在使用的節點最短距離的節點，我使用的是陣列那邊完全穿越它找出該節點的一部分。如何在Dijkstra算法中使用二進制堆？
這部分可以用二進制堆來代替，我們可以計算出O（1）時間節點，但我們還更新在進一步的迭代節點的距離，我將如何整合這堆？
在數組的情況下，我所要做的就是轉到（ith -1）索引並更新該節點的值，但同樣的事情不能在Binary堆中完成，我必須做全面搜索以找出節點的位置，然後進行更新。
是什麼這個問題的解決方法嗎？
這只是一些資料，我發現，而這樣做的一類，我和同學一起分享。我想我會讓人們更容易找到它，並且我已經離開了這篇文章，以便在找到解決方案時能夠回答它。
注意：我假設這個例子中你的圖的頂點有一個ID來跟蹤哪個是哪個。這可能是一個名字，一個數字，無論如何，只要確保你在下面的struct中改變了類型。 如果您沒有這種區分方式，那麼您可以使用指向頂點的指針並比較它們的指向地址。
你面對的是這裏的問題是，在Dijkstra算法，我們被要求在圖形頂點和他們的密鑰存儲在優先級隊列，然後更新者的留在隊列鍵。 但...堆數據結構無法獲取任何不是最小或最後節點的特定節點！
我們能做的最好的事情就是遍歷O（n）時間的堆找到它，然後更新它的密鑰並在O（Logn）上冒泡。這使得更新所有頂點O（n）爲每個單邊，使我們的實現Dijkstra O（mn），方式比最佳O（mLogn）差。
Bleh！一定有更好的方法！
因此，我們需要實現的並不完全是一個標準的基於最小堆的優先級隊列。我們需要一個比標準的4個PQ操作多個操作：
爲了DecreaseKey ，我們需要：
從本質上講，因爲你（I」假設它已經在過去4個月的某個時間實施）可能要使用「基於陣列」的堆實現，這意味着我們需要堆來按順序跟蹤每個頂點及其索引在數組中爲此操作是可能的。
制定一個struct，如：（C++）
struct VertLocInHeap
{
int vertex_id;
int index_in_heap;
};
將讓你保持它的軌道，但存儲這些在一個陣列仍然會給你O（n）的時間用於查找頂點堆。沒有複雜性的提高，而且比以前更復雜。 >。 <
我的建議（如果優化是這裏的目標）：
我實際上使用了一個std::map聲明爲： std :: map m_locations; 在堆中而不是使用結構。第一個參數（Key）是vertex_id，第二個參數（Value）是堆數組中的索引。 由於std::map可以保證O（Logn）搜索，所以它可以很好地用於開箱即用。然後，無論何時您插入或泡沫，您只需m_locations[vertexID] = newLocationInHeap;
簡單的錢。
分析：
潛在上升空間：我們現在有O（LOGN）尋找在P-Q任何給定的頂點。對於冒泡，我們做O（Log（n））運動，對於在數組索引映射中進行O（Log（n））搜索的每個交換，導致O（Log^2（n）
因此，我們有一個Log（n）+ Log^2（n）= O（Log^2（n））操作，用於更新Heap中的單個邊的關鍵值。 Dijkstra alg取O（mLog^2（n））這與理論最佳值非常接近，至少儘可能接近我可以得到它真棒負鼠
下行：我們存儲字面上兩倍的信息，這是一個「現代」問題嗎？不是真的，我的辦公桌可以存儲超過80億個整數，許多現代計算機至少有8GB RAM;但是，它仍然是一個因素。帶有40億個頂點的圖形，這可能會發生比你想象的更頻繁，那麼它會導致一個問題。而且，所有那些額外的讀/寫，可能不會影響分析的複雜性，在某些機器上可能仍然需要時間，特別是如果信息存儲在外部。
我希望這能幫助未來的人，因爲我有一個時間找到所有這些信息的魔鬼，然後拼湊我從這裏，那裏，到處都有的東西，形成這個。我在指責互聯網和睡眠不足。
>>其實，時間分析是錯誤的。幾天後我發現了這一點，並沒有回來。它實際上最終被共'爲O（log^2（n））的'，因爲氣泡-up功能也使用O（日誌（n））的搜索，以更新'STD索引:: map'如它正在執行O（log（n））操作。這是一個O（log（n））操作，O（log（n））times = O（log^2（n））。這是我的不好，最終我會編輯實際的答案來反映這一點......當我減少了幾個馬提尼酒時。 – FireSBurnsmuP
只是注意到我在回答的實際主體中解決了上述時間分析錯誤。希望有幫助。 – FireSBurnsmuP
一個你忘記提及巨大的事情是，如果你使用哈希表，你不再能堆裏面重複的元素存儲由於這樣的事實，在哈希表中的元素必須是唯一的。 – Hatefiend
我跑進使用任何形式的堆的問題是，你需要重新排列節點在堆中。爲了做到這一點，你必須不斷彈出堆中的所有東西，直到找到需要的節點，然後改變重量，並將其重新推入（以及所有其他彈出的部分）。老實說，只是使用一個數組可能會更有效，更容易編碼。
我解決這個問題的方式是使用紅黑樹（在C++中它只是STL的set<>數據類型）。該數據結構包含一個pair<>元素，它具有double（成本）和string（節點）。由於樹結構，訪問最小元素的效率非常高（我相信C++通過維護指向最小元素的指針可以使效率更高）。
隨着樹，我也保持包含對於給定的節點的距離加倍的陣列。所以，當我需要對樹中的一個節點重新排序時，我只需使用dist數組中的舊距離以及節點名稱在集合中找到它。然後，我將從樹中移除該元素，然後將其重新插入到具有新距離的樹中。要搜索節點O(log n)並插入節點O（log n），因此重新排序節點的成本爲O(2 * log n) = O(log n)。對於二進制堆，它同時具有用於插入和刪除的O(log n)（並且不支持搜索）。因此，以刪除所有節點爲代價，直到找到所需的節點爲止，更改其權重，然後再插入所有節點。節點重新排序後，我將更改陣列中的距離以反映新距離。
老實說，我不能想出一種方法來修改一個堆，使其能夠動態地改變節點的權重，因爲堆的整個結構是基於節點維護的權重。
此算法：http://algs4.cs.princeton.edu/44sp/DijkstraSP.java.html通過使用「索引堆」：http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html解決了此問題，它基本上維護從鍵到數組索引的映射列表。
我會使用除Min-Heap數組之外的哈希表執行此操作。
散列表具有散列編碼爲節點對象的鍵和值，這些節點位於最小堆arrray中的索引值。
然後，無論何時您在min-heap中移動某些東西，只需要相應地更新散列表即可。因爲在最小堆中每個操作最多移動2個元素（即它們被交換），並且我們的每次移動的成本爲O（1）來更新哈希表，那麼我們不會損壞該哈希表的漸近界最小堆操作。例如，minHeapify是O（lgn）。我們只是每minHeapify操作添加2個O（1）哈希表操作。因此總的複雜性仍然是O（lgn）。
請記住，您將需要修改任何方法，在最小堆中移動您的節點來執行此跟蹤！例如，minHeapify（）需要修改，看起來像這樣用Java：
Nodes[] nodes;
Map<Node, int> indexMap = new HashMap<>();
private minHeapify(Node[] nodes,int i) {
int smallest;
l = 2*i; // left child index
r = 2*i + 1; // right child index
if(l <= heapSize && nodes[l].getTime() < nodes[i].getTime()) {
smallest = l;
}
else {
smallest = i;
}
if(r <= heapSize && nodes[r].getTime() < nodes[smallest].getTime()) {
smallest = r;
}
if(smallest != i) {
temp = nodes[smallest];
nodes[smallest] = nodes[i];
nodes[i] = temp;
indexMap.put(nodes[smallest],i); // Added index tracking in O(1)
indexMap.put(nodes[i], smallest); // Added index tracking in O(1)
minHeapify(nodes,smallest);
}
}
buildMinHeap，heapExtract應該依賴於minHeapify，這樣一方面主要是固定的，但你需要抽出的密鑰從刪除哈希表也是如此。您還需要修改decreaseKey以跟蹤這些更改。一旦修復了，那麼插入也應該是固定的，因爲它應該使用decreaseKey方法。這應該涵蓋所有的基礎，並且不會改變算法的漸近邊界，並且仍然可以繼續爲優先級隊列使用堆。
請注意，Fibonacci Min Heap在此實現中實際上比標準Min Heap更受歡迎，但這是完全不同的蠕蟲罐。
我使用下面的方法。每當我向堆中插入內容時，我都會傳遞一個指向整數的指針（這個內存位置由我擁有，而不是堆），它應該包含由堆管理的數組中元素的位置。所以如果堆中的元素序列被重新排列，它應該更新這些指針指向的值。
所以對於Dijkstra算法algirithm我創建一個posInHeap陣列的SIZEn的。
希望，代碼將使其更清晰。
template <typename T, class Comparison = std::less<T>> class cTrackingHeap
{
public:
cTrackingHeap(Comparison c) : m_c(c), m_v() {}
cTrackingHeap(const cTrackingHeap&) = delete;
cTrackingHeap& operator=(const cTrackingHeap&) = delete;
void DecreaseVal(size_t pos, const T& newValue)
{
m_v[pos].first = newValue;
while (pos > 0)
{
size_t iPar = (pos - 1)/2;
if (newValue < m_v[iPar].first)
{
swap(m_v[pos], m_v[iPar]);
*m_v[pos].second = pos;
*m_v[iPar].second = iPar;
pos = iPar;
}
else
break;
}
}
void Delete(size_t pos)
{
*(m_v[pos].second) = numeric_limits<size_t>::max();// indicate that the element is no longer in the heap
m_v[pos] = m_v.back();
m_v.resize(m_v.size() - 1);
if (pos == m_v.size())
return;
*(m_v[pos].second) = pos;
bool makingProgress = true;
while (makingProgress)
{
makingProgress = false;
size_t exchangeWith = pos;
if (2 * pos + 1 < m_v.size() && m_c(m_v[2 * pos + 1].first, m_v[pos].first))
exchangeWith = 2 * pos + 1;
if (2 * pos + 2 < m_v.size() && m_c(m_v[2 * pos + 2].first, m_v[exchangeWith].first))
exchangeWith = 2 * pos + 2;
if (pos > 0 && m_c(m_v[pos].first, m_v[(pos - 1)/2].first))
exchangeWith = (pos - 1)/2;
if (exchangeWith != pos)
{
makingProgress = true;
swap(m_v[pos], m_v[exchangeWith]);
*m_v[pos].second = pos;
*m_v[exchangeWith].second = exchangeWith;
pos = exchangeWith;
}
}
}
void Insert(const T& value, size_t* posTracker)
{
m_v.push_back(make_pair(value, posTracker));
*posTracker = m_v.size() - 1;
size_t pos = m_v.size() - 1;
bool makingProgress = true;
while (makingProgress)
{
makingProgress = false;
if (pos > 0 && m_c(m_v[pos].first, m_v[(pos - 1)/2].first))
{
makingProgress = true;
swap(m_v[pos], m_v[(pos - 1)/2]);
*m_v[pos].second = pos;
*m_v[(pos - 1)/2].second = (pos - 1)/2;
pos = (pos - 1)/2;
}
}
}
const T& GetMin() const
{
return m_v[0].first;
}
const T& Get(size_t i) const
{
return m_v[i].first;
}
size_t GetSize() const
{
return m_v.size();
}
private:
Comparison m_c;
vector< pair<T, size_t*> > m_v;
};
另一種解決方案是「延遲刪除」。您只需再次插入節點，以新的優先級堆棧，而不是減少關鍵操作。所以，在堆中會有另一個節點的副本。但是，該節點在堆中將比以前的任何副本都高。然後，當獲得下一個最小節點時，您可以簡單地檢查節點是否已被接受。如果是，則簡單地省略循環並繼續（懶惰刪除）。
這有一點點表現更差/高內存使用情況，由於堆內部副本。但是，對於某些問題大小，它仍然是有限的（連接數量），並且可能比其他實現更快。
的可能重複的[是否二元堆支持減少鍵操作？]（http://stackoverflow.com/questions/5897604/does-a-binary-heap-support-the-decrease-key-operation） –