Нахождение минимального значения максимального кластера?

Question

Определите предмет как имеющий:

• уникальный идентификатор
• значение
• время создания
• время удаления

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

Я могу отслеживать максимальную стоимость всех живых предметов, используя кучу:

whenCreated(item):
  i = heap.size
  heap-up(item, heap.size)
  heap.size = heap.size + 1
  max-value = heap[0]

whenDeleted(item):
  ktem = heap[heap.size - 1]
  heap.size = heap.size - 1
  heap-up(ktem, index[item.id])
  heap-down(ktem, index[ktem.id])
  max-value = heap[0]

heap-up(item, i):
  while (i > 0):
    j = floor( (i-1) / 2 )
    jtem = heap[j]
    if (jtem.value > item.value):
      break while
    index[jtem.id] = i 
    heap[i] = heap[i]
    i = j
  index[item.id] = i
  heap[i] = item

heap-down(item, i):
  while (2*i + 1 < heap.size):
    if (2*i + 1 == heap.size or heap[2*i+1].value > heap[2*i+2].value):
      j = 2*i + 1
    else
      j = 2*i + 2          
    jtem = heap[j]
    if (jtem.value < item.value):
      break while
    index[jtem.id] = i
    heap[i] = heap[i] 
    i = j         
  index[item.id] = i
  heap[i] = item

Если у меня есть n предметов, то добавление или удаление одного занимает O(log n) времени.

Теперь предположим, что элементы сгруппированы так, что даны два элемента: a и b, |a.value - b.value| < delta & rArr; a и b находятся в одном кластере.

Например, если у нас есть значения (1, 2, 3, 4, 7, 8, 11, 13, 14, 15, 16) и delta = 2, то кластерами являются (1, 2, 3, 4), (7, 8), (11) и (13, 14, 15, 16).

Я бы хотел отследить минимальное значение кластера, которое содержит максимальное жизненное значение. Я могу сделать это, считывая значения из кучи по порядку, пока не найду разрыв между значениями размера, превышающими delta Однако это занимает O(n) времени, что кажется довольно неэффективным.

Существует ли алгоритм O(log n) для отслеживания минимального значения этого кластера?

Answer 1

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

Предположим, что мы не делали кластеризацию. В этом случае вы можете просто сохранить все элементы в сбалансированном бинарном дереве поиска, чтобы получить O (log n) вставки, удаления и find-min. Но с кластеризацией это меняется. Мое предложение состоит в том, чтобы поддерживать BST кластеров, отсортированных по диапазону значений, хранящихся в кластере, где каждый кластер представлен в виде дерева отображения узлов, которые он содержит.

Чтобы вставить элемент в структуру данных, выполните поиск в BST для предшественника и преемника рассматриваемого элемента. Если узел не принадлежит ни одному из этих кластеров, создайте одноэлементное дерево отображения из этого узла и вставьте его в BST. Если он содержится ровно в одном из двух найденных вами кластеров, вставьте его в этот кластер. Если он содержится в обоих кластерах, удалите оба кластера из BST, объедините их в один кластер, вставьте новый узел в этот кластер, а затем снова вставьте кластер в BST. Время поиска во всех случаях в O (log n), чтобы найти два кластера, затем O (log n) амортизированное время для вставки в кластер. Слияние двух деревьев сплайнов здесь действительно быстро; поскольку кластеры ранее не были объединены, одно дерево содержит значения, которые все строго больше, чем все значения в другом дереве, поэтому объединение может быть выполнено за время амортизации O (log n) путем удаления указателей. Стоимость удаления двух деревьев и добавления их обратно также составляет O (log n).

Чтобы найти минимальное значение максимального кластера, найдите максимальный кластер в BST за время O (log n), затем найдите минимальный элемент кластера, который вы найдете за время амортизации O (log n).

Чтобы удалить элемент, найдите кластер, в котором он находится, за O (log n). Если он находится в своем собственном кластере, удалите этот кластер из дерева. Если нет, удалите элемент из кластера, в котором он находится, а затем найдите его предшественника и преемника в этом кластере. Если они находятся в дельте друг от друга, то кластер все еще в порядке, и мы сделали. В противном случае кластер должен быть разделен. За время амортизации O (log n) разбейте кластер на кластер узлов, меньших или равных предшественнику и превышающих или равных преемнику, затем снова вставьте оба кластера в дерево.

В целом, это дает O (log n), амортизируемую для каждой операции.

Надеюсь, это поможет!

Answer 2

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

Я не уверен, как осуществляется кластеризация (вы можете создать несколько кластеров, удовлетворяющих упомянутому дельта-условию. Почему вы выбрали именно эту кластеризацию?). Вы также можете рассмотреть возможность иметь одно гигантское двоичное дерево поиска для хранения всех значений и обозначить некоторые узлы как «головки кластеров» (т.е. элементы в поддереве, содержащем этот узел, являются кластером). Таким образом, вы легко сможете создавать и удалять новые кластеры.