如何实现以下算法？

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)); 
}