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

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

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

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

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

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 | ⇒ a и b находятся в одном кластере.