CODEWITHSUNDEEP
c++algorithm
Martin Drozdik
Martin Drozdik

Reputation: 13303

How to implement the following algorithm?

I am sorry for the enigmatic title. Here is my problem:

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

I am trying to implement a procedure, which would trim a list of these items to a specified size:

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

The algorithm that needs to be implemented is:

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

I have sofar considered 2 approaches:

1. The heap

Construct a heap from all the values. Heap is apropriate, because it can find and remove the minimal element in O(1) and can be constructed in O(n).

After each removal, locate all the neighbors in the heap, recomputeValue() and update their position in the heap.

So I have done some shallow study of the Heap datastructure on Wikipedia and Boost The problem is that it seems that the Heap does not provide a fast way to locate elements in it.

2. The hashtable

Sort the list by the value. Construct a hash table mapping the pointers Item* to iterators pointing to them in the linked list. Then each time I remove the top (minimal) item from the list, I find all its neighbors in the list in constant time thanks to the hashtable. Then for each neighbor recomputeValue() and update its position in the list and the corresponding iterator in the hashtable.

Maybe the need for a hashtable would be eliminated if I used an ordered skiplist instead of a linked list.

I am new to programming, so my approaches are probably too naive and complicated and I welcome any advice.

To summarize my question:

  1. Is there a way to perform fast lookups in a heap to make #1 feasible?
  2. Is there a container that maintains order of elements and can perform quick lookups, so that I can make #2 cleaner?
  3. How would You handle the problem?

Upvotes: 2

Views: 209

Answers (1)

Potatoswatter
Potatoswatter

Reputation: 137780

This looks like a job for a plain old std::map< double, Item * >. It gives you the minimum element as * items.begin(), and to recompute a neighbor, just do something like

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

Upvotes: 3

Related Questions