K-D 힙

K-D^[1] 힙은 추가 공간 없이 다차원 priority 큐를 구현하는 컴퓨터 과학 데이터 구조입니다.이것은 ^[2]힙의 일반화입니다.k차원 중 하나에서 최소 요소를 효율적으로 삽입, 쿼리 및 최소 요소를 삭제할 수 있으므로 특수한 경우로 이중 엔드 힙이 포함됩니다.

구조.

각각$$k\$displaystyle$ k$($또는 priority) 키(또는 priority)를$$ $가지는{\displaystyle }$ n개 항목의 집합이 주어지면 K-D 힙은 그것들을 2개의 조건을 만족하는 바이너리 트리로 정리합니다.

• 완전한 바이너리 트리입니다.이는 왼쪽부터 채워야 하는 마지막 레이어를 제외하고 꽉 찼다는 것을 의미합니다.
• k-d 힙 순서를 만족합니다.

k-d 힙 순서의 속성은 일반 힙의 힙 속성과 유사합니다.다음과 같은 경우 힙은 k-d 힙 순서를 유지합니다.

• 루트의 노드는 트리 전체에서 가장 작은1번째 속성을 가집니다.
• 루트가 아닌 다른 노드v는 부모 w가 부모에 의해 루트된 서브트리의 최소i번째 속성을 가질 경우 v는 v에 의해 루트된 서브트리 전체의${\displaystyle }$최소i번째 속성을 가집니다(${\displaystyle i}$ ${\displaystyle mod}$ k${\displaystyle }$)${\displaystyle }$+ $(\displaystyle (i\mod$ k$)+1$$}).$

이 구조의 결과 중 하나는 가장 작은 1차 특성 요소가 루트에 포함되며, 또한 모든 i에 대한 가장 작은 i차 특성 요소가 첫 번째 k 레벨에 포함된다는 것이다.

운용

n개의 항목에서 K-D 힙을 만들려면 O(n) 시간이 걸립니다.다음의 조작이 서포트되고 있습니다.

• 시간 O(log n)에 새 항목 삽입
• 일정 시간 동안 임의의 차원에 있는 최소 키로 항목 검색
• 시간 O(log n)의 임의의 차원에 최소 키가 있는 항목을 삭제합니다.
• 힙의 위치가 알려진 것으로 가정하여 시간 O(log n) 내에 힙의 임의 항목을 삭제 또는 수정합니다.

중요한 것은 이러한 작업에 숨겨진 상수는 차원 수인 $상대적$인 k$\displaystyle$ k$\backslash$이기 때문에 K-D 힙은 매우 많은 차원을 가진 애플리케이션에서는 실용적이지 않다는 것입니다.

레퍼런스