Динамическая структура данных в C для упорядочивания объектов time_t?

Question

Мне нужно добавить неизвестное количество раз, используя pthreads, в структуру данных и упорядочить их в первую очередь, кто-нибудь может порекомендовать для этого хорошую структуру (связанный список / список массивов)?

Answer 1

Если вам просто нужно заказать в конце, используйте связанный список для хранения pthreads, поддерживающих добавление count записей. Затем создайте массив размером count, скопируйте элементы во вновь созданный массив и удалите их из списка. Наконец, отсортируйте массив, используя qsort.

Если вам нужно вести упорядоченный список потоков, используйте heap

Первый подход будет иметь следующую сложность

O(n) for Insert
O(nlog(n)) for Sorting

Поздний подход будет иметь

O(nlog(n)) for Insert and Fetching

Вы также можете увидеть очередь приоритетов

Обратите внимание, что если вы открыты для использования STL, вы можете выбрать STL priority_queue

С точки зрения памяти, последний будет использовать больше памяти, поскольку вам нужно хранить два указателя на узел.

Answer 2

Связанный список будет O(n) при поиске места, куда должен идти новый объект, но постоянным при его вставке.

Динамический список массивов / массивов будет O(log(n)) найти правильное место, но наихудший случай вставки O(n), так как вам нужно будет переместить все значения за точку вставки на одну.

Если вам не нужен произвольный доступ или, по крайней мере, до конца, вы можете использовать кучу, O(log(n)) вставку, после того, как вы закончите, вы можете извлечь их в O(log(n)) каждый,так что O(n*log(n)) для всех из них.

И, возможно, есть (вероятно, основанная на дереве) структура, которая может сделать все это в O(log(n)) (красно-черное дерево?).

Итак, в конце концов, все сводитсякак именно вы хотите его использовать.

Редактировать: Посмотрел красно-черные деревья и похоже, что они O(log(n)) search ("amortized O(1)", согласнов Википедии), вставки и удаления, так что это может быть то, что вы хотите.