Эффективная структура данных для доступа по идентификатору и поиска взвешенного случайного элемента

Question

Не могли бы вы помочь мне со структурой данных, которая позволяет выполнять операции O(logN) (или хотя бы O(sqrtN)) для следующего:

1. Вставить элемент, имеющий ID (int64_t) и health (double)
2. Удалить элемент с помощью ID
3. Найдите элемент, взвешенный случайным образом по health

Предпочтительный язык - C ++ или C. Под взвешенной случайностью я подразумеваю следующее:

Рассмотрим totalHealth=Sum(health[0], health[1], ..., health[N-1]). Мне нужна быстрая (как описано выше) операция, которая эквивалентна:

1. Вычислить const double atHealth = rand_uint64_t()*totalHealth/numeric_limits<uint64_t>::max();
2. Перебрать i=0 to N-1, чтобы найти первое i, такое, что Sum(health[0], health[1], ..., health[i]) >= atHealth

Ограничения: health[i] > 0, rand_uint64_t() возвращает равномерно распределенное целочисленное значение от 0 до numeric_limits<uint64_t>::max().

То, что я пробовал до сих пор, является C ++ unordered_map, который позволяет быстро (Θ(1)) вставлять ID и удалять ID, но операция # 3 по-прежнему линейна в N, как описано в моем псевдокоде выше.

Вы помощь очень ценится!

Answer 1

Я не могу придумать, как это сделать с существующими контейнерами STL, но я могу придумать способ сделать это, если вы хотите создать свое собственное двоичное дерево. Хитрость в том, что каждый узел поддерживает общее состояние всех узлов слева от него (не нужно беспокоиться об узлах справа, как вы увидите ниже). Затем, если вы пройдетесь по дереву в порядке идентификатора, вы также сможете вычислить «совокупное здоровье», также в порядке идентификатора, за log(n) время. Таким образом, дерево сортируется как по идентификатору, так и по совокупному состоянию, и вы можете выполнять поиск за log(n) времени либо по идентификатору, либо по «совокупному состоянию». Например, рассмотрим очень простое дерево вроде следующего:

         ID: 8
         h: 10
         chl: 15
   +-------|--------+
   |                |
   ID: 4          ID: 10
   h: 15          h: 7
   chl: 0         chl: 0

в приведенном выше примере h - это состояние узла, а chl - это совокупное состояние всех узлов слева от него. Таким образом, общее состояние всех узлов, указанных выше, составляет 15 + 10 + 7 = 32 (и я предполагаю, что вы ведете этот счет отдельно, хотя вы также можете правильно отслеживать совокупное состояние узлов, и вам это не нужно). Давайте рассмотрим 3 случая:

1. Вы вычисляете atHealth < 15. Затем на первом узле вы видите, что ваше значение меньше, чем chl, поэтому вы знаете, что вам нужно go влево, и вы попадаете на правильный лист.
2. Вы вычисляете atHealth >= 15 < 25, поэтому вы знаете, что это> 15, поэтому вы не go осталось на root, узел, в котором вы находитесь, имеет здоровье 10, а 10 + 15 означает, что совокупное здоровье на этом узле составляет от 15 до 25, так что вы в порядке .
3. Вы вычисляете atHealth >= 25. Каждый раз, когда вы посещаете узел и go справа, вы должны добавлять chl и h узла, на котором вы были, чтобы продолжать вычислять совокупное здоровье при обходе дерева, чтобы вы знали, что начинаете с 10 + 25 = 25, когда вы go правы, и вы добавите это к h или chl любого узла, с которым вы столкнетесь после этого. Таким образом, вы можете быстро обнаружить, что узел справа является правильным.

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

Очевидно, что все усложняется, если вы хотите поддерживать сбалансированное дерево, но это все равно -бл.