2

我很抱歉这个神秘的标题。这是我的问题：

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

到目前为止，我已经考虑了 2 种方法：

1. 堆

从所有值构造一个堆。堆是合适的，因为它可以在 O(1) 中找到并删除最小元素，并且可以在 O(n) 中构建。

每次删除后，定位堆中的所有邻居，recomputeValue()并更新它们在堆中的位置。

所以我在Wikipedia和Boost上对 Heap 数据结构做了一些浅显的研究， 问题是Heap 似乎没有提供快速定位其中元素的方法。

2.哈希表

按值对列表进行排序。构造一个哈希表，将指针 Item* 映射到链表中指向它们的迭代器。然后每次我从列表中删除顶部（最小）项目时，由于哈希表，我会在恒定时间内找到列表中的所有邻居。然后对于每个邻居recomputeValue()并更新其在列表中的位置和哈希表中的相应迭代器。

如果我使用有序的跳过列表而不是链表，也许就不需要哈希表了。

我是编程新手，所以我的方法可能过于天真和复杂，我欢迎任何建议。

总结一下我的问题：

  1. 有没有办法在堆中执行快速查找以使 #1 可行？
  2. 是否有一个容器可以保持元素的顺序并可以执行快速查找，以便我可以使#2 更清洁？
  3. 你会如何处理这个问题？
4

1 回答 1

3

这看起来像是一个普通老人的工作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 ) );
}
于 2013-03-07T09:39:42.433 回答