d-ary 더미

d-ary 힙 또는 d-heap은 우선 순위 대기열 데이터 구조로, 노드에 2 대신 d 하위 항목이 있는 이진 힙을 일반화한다.^[1][2][3]따라서 이진 힙은 2-heap이고, 3-heap은 3-heap이다.타르잔과^[2] 옌센 등에 따르면,^[4] d-ary haps는 도널드 B에 의해 발명되었다. 1975년 존슨.^[1]

이 데이터 구조는 최소 삭제 작업 속도를 느리게 하여 바이너리 힙보다 감소 우선 작업을 더 빨리 수행할 수 있게 한다.이러한 트레이드오프는 삭제 최소 연산보다 우선 연산 감소가 더 일반적인 Dijkstra 알고리즘과 같은 알고리즘의 실행 시간 단축으로 이어진다.^[1][5]또한 d-ary haps는 이진 힙보다 메모리 캐시 동작이 더 뛰어나 이론적으로 최악의 경우 실행 시간이 더 많음에도 불구하고 실제로 더 빨리 실행될 수 있다.^[6]바이너리 힙과 마찬가지로 d-ary 힙은 힙에 항목 배열을 저장하는 데 필요한 추가 스토리지를 사용하지 않는 인플레이스 데이터 구조다.^[2][7]

데이터 구조

d-ary 힙은 n개의 항목 배열로 구성되며 각 항목에는 관련 우선 순위가 있다.이러한 항목은 전체 d-arli 트리의 노드로 볼 수 있으며, 첫 번째 통과 순서로 나열된다. 즉, 배열 위치 0에 있는 항목(영기준 번호 매기기 사용)이 트리의 루트를 형성하고, 위치 1에서 d에 있는 항목은 하위 항목이며, 다음 d 항목은² 손자 항목이다.따라서 위치 i에 있는 항목의 상위(모든 i > 0)는 위치 ⌊(i - 1)/d/에 있는 항목이며, 그 하위 항목은 위치 di + 1 ~ d에 있는 항목이다.힙 속성에 따르면, 최소 heap에서는 각 항목이 적어도 상위 항목만큼 큰 우선 순위를 가지며, 최대 heap에서는 각 항목이 상위 항목보다 크지 않은 우선 순위를 가진다.^[2][3]

최소 힙의 최소 우선 순위 항목(또는 최대 힙의 최대 우선 순위 항목)은 항상 배열의 위치 0에서 찾을 수 있다.우선 순위 대기열에서 이 항목을 제거하려면 어레이의 마지막 항목 x가 해당 위치로 이동되고 어레이의 길이가 1씩 줄어든다.그런 다음 항목 x와 해당 하위 항목이 힙 속성을 충족하지 못하는 동안 항목 x는 하위 항목 중 하나(최소 히프에서 우선 순위가 가장 작은 항목 또는 최대 히프에서 우선 순위가 가장 큰 항목)와 스왑되어 트리 아래쪽으로 이동하고 어레이 나중에 힙 속성을 충족할 때까지 해당 항목을 이동시킨다.동일한 하향 스와핑 절차를 사용하여 최소 힙에서 항목의 우선순위를 높이거나 최대 힙에서 항목의 우선순위를 낮출 수 있다.^[2][3]

힙에 새 항목을 삽입하려면 항목을 어레이 끝에 추가한 다음, 힙 속성을 위반하는 동안 상위 항목과 교환하여 트리에서 위쪽으로 이동하고 어레이에서 이전까지 힙 속성이 충족될 때까지 해당 항목을 이동하십시오.동일한 상향 스왑 절차를 사용하여 최소 힙에서 항목의 우선순위를 낮추거나 최대 힙에서 항목의 우선순위를 높일 수 있다.^[2][3]

n개의 항목 배열에서 새 힙을 생성하려면, 각 항목에 대해 하향 교환 절차를 적용하여 위치 n - 1의 항목에서 시작하여 위치 0의 항목에서 끝나는 역순으로 항목을 반복할 수 있다.^[2][3]

분석

항목이 n개인 d-ary 힙에서 상향 스왑 절차와 하향 스왑 절차 모두 로그 n_d = 로그 n / 로그 d 스왑만큼 수행할 수 있다.상향 스왑 절차에서 각 스왑은 상위 항목과 단일 비교를 포함하며 일정한 시간이 걸린다.따라서 힙에 새 항목을 삽입하거나, 최소 힙에서 항목의 우선순위를 낮추거나, 최대 힙에서 항목의 우선순위를 높이는 시간은 O(log n / log d)이다.하향 스와핑 절차에서 각 스왑은 d 비교를 포함하며 O(d) 시간이 소요된다. 즉, 자녀의 최소 또는 최대값을 결정하는 데 d - 1 비교가 필요하고, 스왑이 필요한지 여부를 결정하기 위해 부모와의 비교가 한 번 더 필요하다.따라서 루트 항목을 삭제하거나, 최소 힙에서 항목의 우선순위를 증가시키거나, 최대 힙에서 항목의 우선순위를 감소시키는 시간은 O(d log n / log d)이다.^[2][3]

n개 항목 집합에서 d-ary 힙을 생성할 때, 대부분의 항목은 d-ary 트리의 잎을 결국 수용할 위치에 있으며, 해당 항목에 대해 하향 스와핑은 수행되지 않는다.대부분의 n/d + 1 항목은 리브가 아니며, 교환할 아이를 찾는 데 O(d) 시간을 들여 한 번 이상 아래쪽으로 교환할 수 있다.대부분의 n/d² + 1 노드는 두 번 하향 스왑될 수 있으며, 첫 번째 기간에 이미 계산된 비용을 초과하는 두 번째 스왑에 대한 추가 O(d) 비용이 발생할 수 있다.따라서 이러한 방식으로 힙을 생성하는 총 시간은 다음과 같다.

${\displaystyle \sum _{i=1}^{\log _{d}n}\왼쪽 사진\frac {n}{d^{i}}+1\오른쪽)O(d)=O(n).}$^[2][3]

위의 정확한 값(d-ary 힙을 구성하는 동안 최악의 경우 비교 횟수)은 다음과 같은 것으로 알려져 있다.

${\displaystyle {\frac {d}{d-1}}(n-s_{d}(n))-(d-1-(n{\bmod {d}}))\left(e_{d}\left(\left\lfloor {\frac {n}{d}}\right\rfloor \right)+1\right)}$,^[8]

여기서 s_d(n)는 n의 표준 base-d 표시의 모든 자릿수를 합한 것이고_d e(n)는 n의 인자화에서 d의 지수를 나타낸다.이 감소한다.

${\displaystyle \mathrm{2n}}$- ${\displaystyle \mathrm{2초}}$ ${\displaystyle {2\mathrm{}}_{}}$( n${\displaystyle }$)${\displaystyle }$- e ${\displaystyle {2\mathrm{}}_{}}$( ${\displaystyle n}$) ${\displaystyle 2n-2s_{2}(n)-e_{2}(n$^[8]

d = 2 및 to에 대해

${\displaystyle \frac{3}{}}$ ${\displaystyle 2}$( n -${\displaystyle {s\mathrm{}}_{}}$ ${\displaystyle 3{}_{}}$( n${\displaystyle }$)${\displaystyle }$- ${\displaystyle 2}$ ${\displaystyle {e\mathrm{}}_{}}$ ${\displaystyle {}_{}}$( n${\displaystyle }$)${\displaystyle }$- ${\displaystyle e}$ ${\displaystyle {}_{}}$( ${\displaystyle n}$- ${\displaystyle 1}$) ${\displaystyle {\frac {3}{2$}}($n-s_{3})(n)-2e_{3}(n)-{3}(n-1$)$$^[8],

d = 3의 경우.

삽입 및 삭제-min 작업이 있는 d-ary 힙의 공간 사용량은 힙의 항목 목록을 포함하는 어레이 이외의 추가 저장소를 사용하지 않기 때문에 선형이다.^[2][7]기존 항목의 우선순위에 대한 변경이 지원되어야 한다면, 항목에서 힙의 위치로 포인터를 유지해야 하며, 다시 선형 저장만 사용한다.^[2]

적용들

m 가장자리와 n 정점이 있는 그래프에서 작동할 경우, 최단 경로에 대한 Dijkstra의 알고리즘과 최소 스패닝 트리에 대한 Prim의 알고리즘 모두 삭제-최소 연산 및 m 감소-우선 연산 수가 있는 최소-heap을 사용한다.d)m/n과d-ary 더미를 사용하여, 운영 이 두가지 형태의 총번 서로 충돌해서, O(mlogm/n n)는 알고리즘을은, 이러한 알고리즘을 할 때 모서리의 수가 급격하게 vert의 수가 보다 큰 경우 이진 힙 버전의 O(m로그 n)러닝 타임에 대한 향상하는 총 시간에 균형을 이룰 수 있다.ices.^[1][5] 대체 우선 순위 대기열 데이터 구조인 피보나치 힙은 훨씬 더 나은 이론적 실행 시간 O(m + n log n)을 제공하지만, 실제로 d-ary 힙은 일반적으로 이 애플리케이션의 피보나치 힙보다 더 빠르고 종종 더 빠르다.^[9]

4-hips는 삭제-min 작업에서도 실제로 2진수보다 더 좋은 성능을 발휘할 수 있다.^[2][3]또한 d-ary 힙은 일반적으로 시스템의 캐시 메모리 크기를 초과하는 힙 크기의 경우 이진 힙보다 훨씬 더 빠르게 실행되며, 이진 힙은 일반적으로 d-ary 힙보다 캐시 누락 및 가상 메모리 페이지 장애가 더 많이 필요하며, 각 힙은 d-ary 힙의 추가 비교로 인해 발생하는 추가 작업보다 훨씬 많은 시간이 소요된다.이진 힙과 비교.^[6][10]

참조

외부 링크

• D-Heap 지원을 통한 일반화 힙의 C++ 구현