Definiowanie elementu jako posiadające:Ustalanie minimalnej wartości maksymalnej klastra?
- unikatowy identyfikator
- wartość
- czas tworzenia
- delecja czas
Mam strumieni dwa wejścia - jedno, co mnie informuje kiedy element jest tworzony, taki, który informuje mnie, kiedy przedmiot zostanie usunięty. Zadzwoń do przedmiotu, który został utworzony, ale nie zniszczony "żywy".
mogę śledzić maksymalną wartość wszystkich żywych elementów wykorzystujących sterty:
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
Jeśli mam n przedmioty, a następnie dodanie lub usunięcie weźmie O(log n) czasu.
Teraz załóżmy elementy skupione są takie, że biorąc pod uwagę dwa elementy, a i b, |a.value - b.value| < delta ⇒ a i b są w tym samym klastrze.
Na przykład, jeśli mamy wartości (1, 2, 3, 4, 7, 8, 11, 13, 14, 15, 16) i delta = 2, to klastry są (1, 2, 3, 4), (7, 8), (11) i (13, 14, 15, 16).
Chciałbym śledzić minimalną wartość klastra, która zawiera maksymalną żywą wartość. Mogę to zrobić, odczytując wartości poza stertą, dopóki nie znajdę przerwy między wartościami większymi niż równe delta. Jednak zajmuje to godzinę O(n), co wydaje się raczej nieefektywne.
Czy istnieje algorytm O(log n) do śledzenia minimalnej wartości tego klastra?
Czy klastry są przechodnie? Na przykład, jeśli delta wynosi 2, to 1, 2, 3, 4, 5 i 6 wszystko w tym samym klastrze? – templatetypedef
Wątpię, czy możesz to zrobić tylko z obecną stertą. Wygląda na to, że potrzebujesz wydajnej, osobnej struktury danych. Rozłączny zestaw byłby dobry, chociaż twoje klastry mogą się scalać, a następnie rozdzielać, więc potrzebujesz czegoś, co pozwala na separację (która nie znajduje się w union-find), podobnie jak wyrafinowanie partycji. – davin
Odpowiedź templatetypedef działa, choć wydaje się trudnym wdrożeniem. Jeśli nie spodziewasz się wielu przypadków granicznych, być może proste rozwiązanie 'O (n)' jest warte zachodu. Oznacza to, że rzadko zdarza się, że koniec klastra zmienia się często, to nie koniec świata. Możesz go nieco poprawić, przechodząc do BST i utrzymując pojedynczy wskaźnik, a następnie twoja operacja 'O (n)' nie występuje przy usuwaniu, tylko w insertach, a nawet wtedy, jeśli spodziewasz się małych klastrów względem 'n' nie powinno być zauważalne. – davin