Структура с чрезвычайно быстрым временем вставки

Как насчет формы списка пропуска, в частности "индексированного списка пропуска" в связанной статье? . Это должно дать O (lg N) вставку и поиск, а также O (1) доступ к первому узлу для обоих ваших вариантов использования.

--Редактировать--

Когда я думаю об алгоритмах O(1), я думаю о методах счисления. Вот вставка O(1) с возвращенным рангом. Идея состоит в том, чтобы разбить ключ на фрагменты и вести подсчет всех вставленных элементов, имеющих этот префикс. К сожалению, константа велика (‹=64 разыменования и добавления), а объем памяти равен O(2 x 2^INT_BITS), что ужасно. Это версия для 16-битных целых чисел, расширение до 32 бит должно быть простым.

int *p1;int *p2;int *p3;int *p4;
void **records;
unsigned int min = 0xFFFF;

int init(void)     {
   p1 = (int*)calloc(16,sizeof(int));
   p2 = (int*)calloc(256, sizeof(int));
   p3 = (int*)calloc(4096, sizeof(int));
   p4 = (int*)calloc(65536,sizeof(int));
   records = (void**)calloc(65536,sizeof(void*));
   return 0;
}

//records that we are storing one more item, 
//counts the number of smaller existing items
int Add1ReturnRank(int* p, int offset, int a) {
   int i, sum=0;
   p+=offset;
   for (i=0;i<a;i++)
      sum += p[i];
   p[i]++;
   return sum;
}

int insert(int key, void* data) {
   unsigned int i4 = (unsigned int)key;
   unsigned int i3= (i4>> 4);
   unsigned int i2= (i3>> 4);
   unsigned int i1= (i2>> 4);
   int rank = Add1ReturnRank(p1,0, i1&0xF);
   rank += Add1ReturnRank(p2,i2&0xF0,i2&0xF);
   rank += Add1ReturnRank(p3,i3&0xFF0,i3&0xF);
   rank += Add1ReturnRank(p4,i4&0xFFF0,i4&0xF);
   if (min>key) {min = key;}
   store(&records[i4],data);
   return rank;
}

Эта структура также поддерживает O(1) GetMin и RemoveMin. (GetMin работает мгновенно, Remove имеет константу, аналогичную Insert.)

void* getMin(int* key) {
    return data[*key=min];
}

void* removeMin(int* key)  {
   int next = 0;
   void* data = records[min];
   unsigned int i4 = min;
   unsigned int i3= (i4>> 4);
   unsigned int i2= (i3>> 4);
   unsigned int i1= (i2>> 4);

   p4[i4]--;
   p3[i3]--;
   p2[i2]--;
   p1[i1]--;
   *key = min;
   while (!p1[i1]) {
      if (i1==15) { min = 0xFFFF; return NULL;}
      i2 = (++i1)<<4;
   }
   while (!p2[i2])
      i3 = (++i2)<<4;
   while (!p3[i3])
      i4 = (++i3)<<4;
   while (!p4[i4])
      ++i4;
   min = i4;
   return data;
}

Если ваши данные разрежены и хорошо распределены, вы можете удалить счетчик p4 и вместо этого выполнить сортировку вставками на уровне P3. Это уменьшит затраты на хранение на 16 за счет более высокой вставки в наихудшем случае, когда имеется много похожих значений.

Другой идеей по улучшению хранилища может быть объединение этой идеи с чем-то вроде Extendable Hash. Используйте целочисленный ключ в качестве хеш-значения и ведите подсчет вставленных узлов в каталоге. Выполнение суммирования соответствующих записей словаря во вставке (как указано выше) по-прежнему должно быть O (1) с большой константой, но хранилище уменьшится до O (N)

Дерево статистики заказов, похоже, соответствует вашим потребностям за время O(LogN). Ссылка

Дерево статистики порядка – это расширенная (см. AugmentedDataStructures) версия
BinarySearchTree, которая поддерживает дополнительные операции Rank(x), возвращающие ранг x (т. е. количество элементов с ключами, меньшими или равными x). ) и FindByRank(k), который возвращает k-й наименьший элемент дерева.

Если у вас есть только десятки тысяч элементов, разница в производительности между временем O (LogN) и асимптотической временной сложностью O (1) не так значительна, как вы думали. Например, рассмотрим 100 000 элементов, метод logN всего в 16 раз медленнее.

лог(100 000) / лог(2) = 16,6096405

В этом случае разница в коэффициентах (реализация, накладные расходы) может быть реальной целью оптимизации. Причудливые структуры данных обычно имеют гораздо более высокие накладные расходы из-за сложности наследования (иногда в тысячи раз медленнее). Они, скорее всего, появятся в результате менее совершенной реализации, потому что они реже используются.

Вы должны протестировать (фактически протестировать) различные реализации кучи, чтобы найти одну из них с лучшей реальной производительностью.

Вы говорите, что вам нужна упорядоченная структура данных, что для меня звучит так, будто вам нужно что-то, что может дать все элементы, содержащиеся за время O (n).

Но затем вы говорите, что будете обращаться только к верхнему (наименее?) элементу, предполагая, что вам действительно просто нужно что-то, что может дать минимальное значение, неоднократно - открывая дверь к чему-то с частичным порядком.

Что он?

Если я правильно понимаю ваш вопрос, я бы порекомендовал вам использовать словарь, ключи которого являются рангами, а значения - связанным списком.

С ключами вы можете иметь ранги, а со связанным списком в качестве значений вы можете иметь время вставки O (1). Также в качестве удаления вы можете иметь O (1). Вы можете реализовать стек или очередь с помощью связанного списка, что вам и нужно.

Или вы можете просто использовать двусвязный список, в котором у вас гарантированно будет вставка и удаление O (1). для ранжирования вы можете встроить эту информацию в узлы.