최대 클러스터의 최소값 찾기?

Question

것으로 항목을 정의

• 고유 ID
• 값
• 삭제가

나는 두 개의 입력 스트림을 한 시간 창조 시간 - 나로 알린다 항목이 만들어지면 항목이 삭제 될 때 알려줍니다. 창조되었지만 파괴되지 않은 "살아있는"물건을 부르십시오. 그때 하나가 O(log n) 시간이 소요 추가 또는 삭제, n 항목을 가지고있는 경우에

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 

:

나는 힙을 사용하여 모든 살아있는 항목의 최대 값을 추적 할 수 있습니다.

지금 항목이 두 항목, a 및 b, |a.value - b.value| < delta ⇒ 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 (logn)에 있습니다. 각 클러스터에 대해 별도의 이진 트리를 구성하십시오.

클러스터링이 어떻게 수행되는지 잘 모르겠습니다 (언급 한 델타 조건을 만족하는 다중 클러스터링을 구성 할 수 있습니다. 왜이 특정 클러스터링을 선택 했습니까?). 하나의 거대한 이진 검색 트리를 사용하여 모든 값을 저장하고 일부 노드를 "클러스터 헤드"(즉,이 노드를 포함하는 하위 트리의 요소는 클러스터)로 지정할 수도 있습니다. 이렇게하면 새 클러스터를 쉽게 만들고 삭제할 수 있습니다.

Answer 2

저는 각 작업에 대한 O (log n) 상각 시간을 보장하기 위해 스플레이 트리의 균형 이진 검색 트리를 사용하여이 작업을 수행 할 수 있다고 생각합니다.

클러스터링을 수행하지 않았다고 가정합니다. 이 경우, 균형 잡힌 이진 검색 트리에 모든 요소를 ​​저장하여 O (log n) 삽입, 삭제 및 찾기 - 분을 얻을 수 있습니다. 그러나 클러스터링으로 인해 이러한 변화가 일어납니다. 내 제안은 클러스터에 보유 된 값의 범위로 정렬 된 클러스터의 BST를 유지하는 것입니다. 여기서 각 클러스터는 포함 된 노드의 분출 트리로 표시됩니다.

데이터 구조에 요소를 삽입하려면 BST에서 해당 요소의 전신과 후속을 검색하십시오. 노드가 이러한 클러스터에 속하지 않으면 해당 노드에서 싱글 톤 표시 트리를 작성하여 BST에 삽입하십시오.찾은 두 클러스터 중 하나에 정확히 포함되어 있으면 해당 클러스터에 삽입하십시오. 두 클러스터에 모두 포함되어 있으면 BST에서 두 클러스터를 모두 제거하고 하나의 클러스터로 병합 한 다음 새 노드를 해당 클러스터에 삽입 한 다음 클러스터를 BST에 다시 삽입하십시오. O (log n)의 모든 경우에서 검색 시간을 사용하여 두 개의 클러스터를 찾은 다음 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)은 각 작업에 대해 상각됩니다.

희망이 도움이됩니다.