Какова постоянная структура данных для набора частично упорядоченных элементов?

Мне нужно хранить наборы элементов типа а. Тип a частично упорядочен, поэтому сравнение и может вернуть меньшее, большее, равное или несопоставимое.$a_1$$a_2$

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

Сравнение двух элементов может быть длительным процессом, поэтому было бы интересно минимизировать сравнения. При необходимости можно запомнить звонки оператору сравнения. Теперь я понимаю, что мне нужно будет хранить только антицепи (или, допустим, так). Точнее, операции, которые мне нужно будет выполнить, следующие:

• Удалить элемент из антицепи;
• Попробуйте добавить элемент. Если элемент меньше члена, не добавляйте его, в противном случае добавьте его и удалите каждый элемент меньше его.

Я также могу связать каждый элемент двумя целыми числами, так что если я знаю, что и , то знание мгновенно дает мне . Конечно, не означает a \ not <b ... Поиск целочисленных границ - относительно дешевая операция по сравнению с полным сравнением элементов.$i_1 < a < i_2$$i_3 < b < i_4$$i_2 < i_3$$a < b$$i_2 \not< i_3$$a \not < b$

Статья «Сортировка и отбор в PoSets», написанная Daskalakis, Karp, Mossel, Risensefield, Verbin, 2008, которая описывает динамическое представление PoSets на основе антицепей.

Возможно, вас также заинтересует опубликованная недавно на Arxiv статья «Сжатые позы», выпущенная Munro, Nicholson 2012, и библиография в ней. Их структура данных является статической, но я предполагаю, что следующим шагом будет создание динамической структуры данных.

$O(\lg n)$