deleteMin和按鍵操作搜索的有效數據結構

我有100組A對象，每組對應一個查詢點Qi，1 <= i <= 100。deleteMin和按鍵操作搜索的有效數據結構

class A { 
    int id; 
    int distance; 
    float x; 
    float y; 
}

以我算法的每次迭代中，我選擇一個查詢點Qi並從具有最小距離值對應的設定的對象中提取。然後，我必須在所有100個集合中找到這個特定的對象，用它的id進行搜索，然後刪除所有這些對象。

如果我爲每組對象使用一個堆，使用MIN(distance)提取對象是很便宜的。但是，我不能在其他堆中使用id搜索相同的對象，因爲堆是用距離值組織的。此外，更新堆是昂貴的。

我考慮的另一個選項是使用每個集合的map<id, (distance, x, y)>。通過id搜索（查找操作）的方式很便宜。但是，提取具有最小值的元素需要線性時間（它必須檢查映射中的每個元素）。

有沒有我可以使用的數據結構對於我需要的操作都是有效的？

extract_min（距離）
發現（ID）

提前感謝！

來源

2010-11-15 Tasos Arvanitis

爲你做了一些格式化。請使用編輯框上方的按鈕來正確格式化您的代碼。 – 2010-11-15 16:57:07

不是C++的女孩，所以不能真正提供有意義的答案，但有時對於這種情況，最簡單的解決方案是兩種數據結構：通過索引查找項目的映射或散列表，通過排序的數組/堆/樹設置以找到最小值項目。 – Juliet 2010-11-15 18:18:55

std::map或boost::multi_index

來源

2010-11-15 16:50:54

謝謝，boost :: multi_index完成了這項工作 – 2010-11-17 20:55:16

您可以使用樹形圖。

來源

2010-11-15 16:48:45 AHungerArtist

這實在是一個評論，而不是對問題的回答。請使用「添加評論」爲作者留下反饋。 – stakx 2012-08-17 17:40:53

@stakx尋求一個有效的數據結構並回答數據結構是一個答案。 T – AHungerArtist 2012-08-17 18:02:30

我知道。你的回答沒有錯;它只是很短。例如，如果它解釋了這些信息，它將更具信息性，*爲什麼*樹圖是合適的;或者您描述了樹圖的最重要屬性和操作;或者至少鏈接到能夠完成所有工作的紙張。正如你的回答，你可以發佈它作爲評論。 – stakx 2012-08-17 18:06:03

一種簡單的方法是具有兩個圖對於每一個數據集。第一個包含按id排序的所有數據項。第二個將是multimap和地圖距離，以便您可以輕鬆找出最低距離對應的id。這個將按距離排序，以便找到最便宜的（因爲它將使用距離作爲關鍵）。如果您知道距離始終是唯一的，您可以使用map而不是multimap。

來源

2010-11-15 18:10:42

除了ncluding地圖作爲許多上面建議的，你可以用具有運行復雜性是提取分鐘不變的結構取代你的最小堆。您當前的版本的運行時複雜度爲O（log_2（n））以提取最小。
由於您的距離範圍是小，您可以使用「撥號陣列」算法。這些鍵就像「計數排序」。由於您可能在中有多個項目，但您不關心等價項目的順序，您可以使用雙向鏈接列表作爲數組的項目數據類型。 Andrew Goldberg和Tarjan的論文關於更快的Dijkstra算法詳細說明了這一點。

來源

2016-06-11 08:34:40 nichole

deleteMin和按鍵操作搜索的有效數據結構

回答

相關問題