Data Structure Suggestion For Finding the Smallest Value With Deletions/Updates

user_1805103 0
Viewed 130

I am hoping for a suggestion of a C/C++ data structure(s) to deal with the following problem:

Say you have a series of points (A, B, C, D, ... N) stored in an array/linked list and each point has a value associated with it (A-val, B-val, ...). The value of each point depends in part on its immediate neighbors to the left and right. Thus, A-val depends on N and B, B-val depends on A and C, etc. Thus, ordering matters. Further, two points can have the same val (i.e., A-val can equal B-val).

enter image description here

After the initial values are assigned, you find the point with the smallest val, delete it, and update the vals previously associated with the left neighbor and the right neighbor (who are now neighbors themselves). Thus, if B had the smallest val, you would delete B, update the A-val (which now depends on C) and update the C-val (which now depends on A). The new vals of A and C may be different than each other, higher, lower, or the same as the val for deleted point B, and higher, lower, or the same as their previous vals. A change in the C-val, e.g., does not cause a change in the D-val. Thus, a deletion only effects the prior points' left and right neighbors and does not effect other points. You repeat this process until the smallest val is greater than some arbitrary number.

One way of doing this is to just go through the whole list each time looking for the smallest val. While this approach works, when N is large (e.g., 1000) and your arbitrary number means that only ~100 points will survive, this is slow and close to O(N^2).

I was thinking of maintaining a separate list of vals and points sorted by the vals. But I cannot figure out how you would update this list or possibly have the same list sorted in multiple ways.

Any suggestions appreciated.

data-structures
1 Answers

I think it's got to be custom, because of the combination of 1) sorting, 2) accessing and linking to arbitrary locations, 3) repeated values.

Thoughts

  1. you want to get the lowest value cheaply.
  2. you want cheap insertion and deletion, while maintaining order
  3. you want to be able to reference your objects by their value or address.

I'd make a struct, then make a mapping of value to a set of shared pointers to mystruct's:

struct {
  int val;
  shared_ptr<mystruct> left;
  shared_ptr<mystruct> right;
} mystruct;

map<int, set<shared_ptr<mystruct>>> mydata;

With this setup, you can:

  1. Find the lowest value in O(1)
  2. Find the first node with the lowest value in O(1)
  3. Find the node's neighbors in O(1)
  4. Find the set containing each neighbor in O(logN)
  5. Insert and delete sets in O(logN)

So, the total time to delete one of your nodes + update it's values + maintain sorted order: O(logN)

Map is ordered, so you just grab the first key to get the lowest value (or detect an empty map). I think this will only result in the keys of map getting sorted when a new one is inserted or removed, which is the best you can do, since you can't use a heap and there's no guarantee about neighbors' values relative to each other.

There's a question/concern here: if you want to delete the lowest, does it matter which one?? I'm using a set, but if order matters, you might want to swap that out for a vector and delete from the beginning/end of it.

Here's a (somewhat ugly) proof-of-concept script I wrote up for it:

#include <stdio.h>
#include <set>
#include <vector>
#include <map>
#include <memory>

using namespace std;

struct mystruct {
  int val;
  shared_ptr<mystruct> left;
  shared_ptr<mystruct> right;
  mystruct(int val, shared_ptr<mystruct> left, shared_ptr<mystruct> right) : val(val), left(left), right(right) {}
};


map<int, set<shared_ptr<mystruct>>> mydata;

int main() {

  // **** BEGIN MY CREATING AND DISPLAYING FAKE DATA ****
  // Some random values my fingers picked, with a couple repeats
  vector<int> some_values = {0,45,2,34,5,2,3,5,67,2};
  
  // Create the initial data structure
  shared_ptr<mystruct> first_created (new mystruct(some_values[0],NULL,NULL));
  mydata[some_values[0]].insert(first_created); // first value
  shared_ptr<mystruct> left = first_created;
  for (int i=1; i < some_values.size(); i++) {
    int v = some_values[i];
    shared_ptr<mystruct> newly_created (new mystruct(v,left,NULL));
    mydata[v].insert(newly_created); // connect this to the left
    left->right = newly_created;
    left = newly_created;
  }
  left->right = first_created; // connect first with last
  first_created->left = left; // connect first with last


  // Sanity check
  printf("Initial Conditions\n");
  for (auto it: mydata) {
    for (auto addr: it.second){
      printf("%d  addr=0x%p  left=0x%p (%d) right=0x%p (%d)\n",it.first,addr.get(),addr->left.get(),addr->left->val, addr->right.get(), addr->right->val);
    }
  }
  // **** END MY CREATING AND DISPLAYING FAKE DATA ****
  
  
  // **** BEGIN REMOVING EVERYTHING WITH VAL < X ****
  // Let's remove everything below 5
  int stopAt = 200;
  while (1) {
  
    if (mydata.begin() == mydata.end()) {
      printf("Ran out of data!\n");
      break;
    }
    auto it = mydata.begin();
    printf("First key = %d  Number of map keys=%lu\n",it->first,mydata.size());
    for (auto it: mydata) {
      for (auto addr: it.second){
        int leftval = (addr->left.get()==nullptr) ? 0 : addr->left->val;
        int rightval = (addr->right.get()==nullptr) ? 0 : addr->right->val;
        printf("%d  addr=0x%p  left=0x%p (%d) right=0x%p (%d)\n",it.first,addr.get(),addr->left.get(),leftval, addr->right.get(), rightval);
      }
    }

    if (it->first >= stopAt) {
      printf("Stopping, because the first key (%d) is >= %d (the stop value)\n",it->first,stopAt);
      break;
    }
    if (it->second.empty()) {
      printf("Whoops - we have an empty set!  (This should NEVER happen)\n");
      break;
    }
    
    // OK for ease, we'll pick off the first guy
    shared_ptr<mystruct> deleteMe = *(it->second.begin());
    
    // 1) find the left and right. deletion only affects those
    shared_ptr<mystruct> left = deleteMe->left;
    shared_ptr<mystruct> right = deleteMe->right;
    
    if (left != NULL) {
      
      // 2) remove the left and right from their previous vectors
      mydata[left->val].erase(left); // remove from set
      if (mydata[left->val].empty()) mydata.erase(left->val); // remove from map if set is empty
      bool penultimate = (left==right);
      if (penultimate) {
      }
      
      if (not penultimate) {
        mydata[right->val].erase(right); // remove from set
        if (mydata[right->val].empty()) mydata.erase(right->val); // remove from map if set is empty
      }
      
      // 3) update their values in some way
      left->val += deleteMe->val / 2;
      if (not penultimate) right->val += deleteMe->val / 2;
      
      // 4) update their pointers - skip over the deleted guy
      if (not penultimate) {
        left->right = right;
        right->left = left;
      }
      else {
        left->right = NULL;
        left->left = NULL;
      }
      
      // 5) put them in the right place in the map
      mydata[left->val].insert(left);
      if (not penultimate) mydata[right->val].insert(right);
    }
    
    // 6) finally, delete the O.G.
    mydata[deleteMe->val].erase(deleteMe);
    if (mydata[deleteMe->val].empty()) mydata.erase(deleteMe->val); // remove from map if set is empty
  }
  // **** END REMOVING EVERYTHING WITH VAL < X ****
 

  // **** BEGIN PRINTING RESULTS AND CLOSING DOWN ****
  
  // Results
  printf("Results\n");
  for (auto it: mydata) {
    for (auto addr: it.second){
        int leftval = (addr->left.get()==nullptr) ? 0 : addr->left->val;
        int rightval = (addr->right.get()==nullptr) ? 0 : addr->right->val;
        printf("%d  addr=0x%p  left=0x%p (%d) right=0x%p (%d)\n",it.first,addr.get(),addr->left.get(),leftval, addr->right.get(), rightval);
    }
  }

  // Clean up
  //  -- automatic, due to shared_ptr!

  // **** END PRINTING RESULTS AND CLOSING DOWN ****

 return 0;
}

Here's example output when stopAt = 200. You can see it as it moves along, removing everything, one-by-one. In my script, the left and right neighbors' values increment by half of the deleted value in their update step.

Initial Conditions
0  addr=0x0x55af1c01aee0  left=0x0x55af1c01b690 (2) right=0x0x55af1c01afd0 (45)
2  addr=0x0x55af1c01b0c0  left=0x0x55af1c01afd0 (45) right=0x0x55af1c01b1b0 (34)
2  addr=0x0x55af1c01b390  left=0x0x55af1c01b2a0 (5) right=0x0x55af1c01b420 (3)
2  addr=0x0x55af1c01b690  left=0x0x55af1c01b5a0 (67) right=0x0x55af1c01aee0 (0)
3  addr=0x0x55af1c01b420  left=0x0x55af1c01b390 (2) right=0x0x55af1c01b510 (5)
5  addr=0x0x55af1c01b2a0  left=0x0x55af1c01b1b0 (34) right=0x0x55af1c01b390 (2)
5  addr=0x0x55af1c01b510  left=0x0x55af1c01b420 (3) right=0x0x55af1c01b5a0 (67)
34  addr=0x0x55af1c01b1b0  left=0x0x55af1c01b0c0 (2) right=0x0x55af1c01b2a0 (5)
45  addr=0x0x55af1c01afd0  left=0x0x55af1c01aee0 (0) right=0x0x55af1c01b0c0 (2)
67  addr=0x0x55af1c01b5a0  left=0x0x55af1c01b510 (5) right=0x0x55af1c01b690 (2)
First key = 0  size=7
0  addr=0x0x55af1c01aee0  left=0x0x55af1c01b690 (2) right=0x0x55af1c01afd0 (45)
2  addr=0x0x55af1c01b0c0  left=0x0x55af1c01afd0 (45) right=0x0x55af1c01b1b0 (34)
2  addr=0x0x55af1c01b390  left=0x0x55af1c01b2a0 (5) right=0x0x55af1c01b420 (3)
2  addr=0x0x55af1c01b690  left=0x0x55af1c01b5a0 (67) right=0x0x55af1c01aee0 (0)
3  addr=0x0x55af1c01b420  left=0x0x55af1c01b390 (2) right=0x0x55af1c01b510 (5)
5  addr=0x0x55af1c01b2a0  left=0x0x55af1c01b1b0 (34) right=0x0x55af1c01b390 (2)
5  addr=0x0x55af1c01b510  left=0x0x55af1c01b420 (3) right=0x0x55af1c01b5a0 (67)
34  addr=0x0x55af1c01b1b0  left=0x0x55af1c01b0c0 (2) right=0x0x55af1c01b2a0 (5)
45  addr=0x0x55af1c01afd0  left=0x0x55af1c01aee0 (0) right=0x0x55af1c01b0c0 (2)
67  addr=0x0x55af1c01b5a0  left=0x0x55af1c01b510 (5) right=0x0x55af1c01b690 (2)
First key = 2  size=6
2  addr=0x0x55af1c01b0c0  left=0x0x55af1c01afd0 (45) right=0x0x55af1c01b1b0 (34)
2  addr=0x0x55af1c01b390  left=0x0x55af1c01b2a0 (5) right=0x0x55af1c01b420 (3)
2  addr=0x0x55af1c01b690  left=0x0x55af1c01b5a0 (67) right=0x0x55af1c01afd0 (45)
3  addr=0x0x55af1c01b420  left=0x0x55af1c01b390 (2) right=0x0x55af1c01b510 (5)
5  addr=0x0x55af1c01b2a0  left=0x0x55af1c01b1b0 (34) right=0x0x55af1c01b390 (2)
5  addr=0x0x55af1c01b510  left=0x0x55af1c01b420 (3) right=0x0x55af1c01b5a0 (67)
34  addr=0x0x55af1c01b1b0  left=0x0x55af1c01b0c0 (2) right=0x0x55af1c01b2a0 (5)
45  addr=0x0x55af1c01afd0  left=0x0x55af1c01b690 (2) right=0x0x55af1c01b0c0 (2)
67  addr=0x0x55af1c01b5a0  left=0x0x55af1c01b510 (5) right=0x0x55af1c01b690 (2)
First key = 2  size=6
2  addr=0x0x55af1c01b390  left=0x0x55af1c01b2a0 (5) right=0x0x55af1c01b420 (3)
2  addr=0x0x55af1c01b690  left=0x0x55af1c01b5a0 (67) right=0x0x55af1c01afd0 (46)
3  addr=0x0x55af1c01b420  left=0x0x55af1c01b390 (2) right=0x0x55af1c01b510 (5)
5  addr=0x0x55af1c01b2a0  left=0x0x55af1c01b1b0 (35) right=0x0x55af1c01b390 (2)
5  addr=0x0x55af1c01b510  left=0x0x55af1c01b420 (3) right=0x0x55af1c01b5a0 (67)
35  addr=0x0x55af1c01b1b0  left=0x0x55af1c01afd0 (46) right=0x0x55af1c01b2a0 (5)
46  addr=0x0x55af1c01afd0  left=0x0x55af1c01b690 (2) right=0x0x55af1c01b1b0 (35)
67  addr=0x0x55af1c01b5a0  left=0x0x55af1c01b510 (5) right=0x0x55af1c01b690 (2)
First key = 2  size=7
2  addr=0x0x55af1c01b690  left=0x0x55af1c01b5a0 (67) right=0x0x55af1c01afd0 (46)
4  addr=0x0x55af1c01b420  left=0x0x55af1c01b2a0 (6) right=0x0x55af1c01b510 (5)
5  addr=0x0x55af1c01b510  left=0x0x55af1c01b420 (4) right=0x0x55af1c01b5a0 (67)
6  addr=0x0x55af1c01b2a0  left=0x0x55af1c01b1b0 (35) right=0x0x55af1c01b420 (4)
35  addr=0x0x55af1c01b1b0  left=0x0x55af1c01afd0 (46) right=0x0x55af1c01b2a0 (6)
46  addr=0x0x55af1c01afd0  left=0x0x55af1c01b690 (2) right=0x0x55af1c01b1b0 (35)
67  addr=0x0x55af1c01b5a0  left=0x0x55af1c01b510 (5) right=0x0x55af1c01b690 (2)
First key = 4  size=6
4  addr=0x0x55af1c01b420  left=0x0x55af1c01b2a0 (6) right=0x0x55af1c01b510 (5)
5  addr=0x0x55af1c01b510  left=0x0x55af1c01b420 (4) right=0x0x55af1c01b5a0 (68)
6  addr=0x0x55af1c01b2a0  left=0x0x55af1c01b1b0 (35) right=0x0x55af1c01b420 (4)
35  addr=0x0x55af1c01b1b0  left=0x0x55af1c01afd0 (47) right=0x0x55af1c01b2a0 (6)
47  addr=0x0x55af1c01afd0  left=0x0x55af1c01b5a0 (68) right=0x0x55af1c01b1b0 (35)
68  addr=0x0x55af1c01b5a0  left=0x0x55af1c01b510 (5) right=0x0x55af1c01afd0 (47)
First key = 7  size=5
7  addr=0x0x55af1c01b510  left=0x0x55af1c01b2a0 (8) right=0x0x55af1c01b5a0 (68)
8  addr=0x0x55af1c01b2a0  left=0x0x55af1c01b1b0 (35) right=0x0x55af1c01b510 (7)
35  addr=0x0x55af1c01b1b0  left=0x0x55af1c01afd0 (47) right=0x0x55af1c01b2a0 (8)
47  addr=0x0x55af1c01afd0  left=0x0x55af1c01b5a0 (68) right=0x0x55af1c01b1b0 (35)
68  addr=0x0x55af1c01b5a0  left=0x0x55af1c01b510 (7) right=0x0x55af1c01afd0 (47)
First key = 11  size=4
11  addr=0x0x55af1c01b2a0  left=0x0x55af1c01b1b0 (35) right=0x0x55af1c01b5a0 (71)
35  addr=0x0x55af1c01b1b0  left=0x0x55af1c01afd0 (47) right=0x0x55af1c01b2a0 (11)
47  addr=0x0x55af1c01afd0  left=0x0x55af1c01b5a0 (71) right=0x0x55af1c01b1b0 (35)
71  addr=0x0x55af1c01b5a0  left=0x0x55af1c01b2a0 (11) right=0x0x55af1c01afd0 (47)
First key = 40  size=3
40  addr=0x0x55af1c01b1b0  left=0x0x55af1c01afd0 (47) right=0x0x55af1c01b5a0 (76)
47  addr=0x0x55af1c01afd0  left=0x0x55af1c01b5a0 (76) right=0x0x55af1c01b1b0 (40)
76  addr=0x0x55af1c01b5a0  left=0x0x55af1c01b1b0 (40) right=0x0x55af1c01afd0 (47)
First key = 67  size=2
67  addr=0x0x55af1c01afd0  left=0x0x55af1c01b5a0 (96) right=0x0x55af1c01b5a0 (96)
96  addr=0x0x55af1c01b5a0  left=0x0x55af1c01afd0 (67) right=0x0x55af1c01afd0 (67)
First key = 129  size=1
129  addr=0x0x55af1c01b5a0  left=0x(nil) (0) right=0x(nil) (0)
Ran out of data!
Results
user_151616400
Related