如何實現以下算法？

Question

我很抱歉，神祕的標題。這裏是我的問題：

class Item 
{ 
public: 
    double value; 
    void recomputeValue(); // after this, will probably increase a little, 
          // but never decrease. 
    std::list<Item*> neighbors; // relatively few items 
}; 

我想實現的過程，這將修剪這些物品到指定大小的列表：

void trimToNewSize(std::list<Item*>& items, int newSize); 

，需要加以實現的算法是：

while (size > newSize) 
{ 
    erase item with smallest value; 
    recomputeValue() for all its neighbors; 
} 

我已經考慮SOFAR 2點的方法：

1.堆

從所有值構造一個堆。堆是合適的，因爲它可以找到並刪除O（1）中的最小元素，並且可以在O（n）中構造。

每次刪除後，找到所有的鄰居在堆中，recomputeValue()並更新他們在堆位置。

所以我也做了堆數據結構的一些粗淺的研究上Wikipedia和Boost 的問題是，它似乎是堆不提供快速的方式來定位它元素。

2.哈希表

排序列表由值。構建一個哈希表，將指針Item *映射到指向鏈表中的迭代器。然後，每次我從列表中刪除頂部（最小）項目時，都會因爲哈希表而在列表中持續查找其所有鄰居。然後爲每個鄰居recomputeValue()更新其在列表中的位置以及散列表中的對應迭代器。

也許，如果我用一個有序skiplist，而不是一個鏈表哈希表需要將被淘汰。

我的新節目，所以我的方法可能是太天真了，複雜的，我歡迎任何建議。

總結我的問題：

1. 有沒有在堆中進行快速查找，使＃1可行的方法嗎？
2. 是否有維護元素的順序，可以進行快速查找，這樣我可以做＃2清潔的容器？
3. 你會如何處理這個問題？

Answer 1

這看起來像一個普通的老工作std::map< double, Item * >。它給你作爲* items.begin()的最小元素，並重新計算鄰居，只是像做

typedef std::map< double, Item * > itemsByValue; 
itemsByValue items; 

class Item 
{ 
public: 
    double value; 
    void recomputeValue(); // after this, will probably increase a little, 
          // but never decrease. 
    std::list<itemContainer::iterator> neighbors; // relatively few items 
}; 

for (itemsByValue::iterator i = neighbors.begin(); 
     i != neighbors.end(); ++ i) { 
    Item &item = * neighbor; 
    items.erase(neighbor); 
    item.recomputeValue(); 
    items.insert(std::make_pair(item.value, & item)); 
}