피보나치 힙

피보나치 힙
피보나치 힙
유형	수북이 쌓다
발명된	1984
발명자	마이클 L.프레드만과 로버트 엔드레 타잔
빅 O 표기의 시간 복잡도
알고리즘.
알고리즘.
삽입
검색 최소값
삭제 최소값
감소 키
머지

컴퓨터 과학에서 피보나치 힙은 힙 순서 트리의 집합으로 구성된 priority 큐 연산을 위한 데이터 구조입니다.바이너리 힙 및 이항 힙을 포함한 다른 많은 우선순위 큐 데이터 구조보다 상각 실행 시간이 더 좋습니다.마이클 L. 프레드먼과 로버트 E. 타잔은 1984년에 피보나치 더미를 개발했고 1987년에 과학 저널에 발표했다.피보나치 힙은 실행 시간 분석에 사용되는 피보나치 숫자의 이름을 따서 명명됩니다.

Fibonacci 힙의 경우 find-minimum 조작은 상각된 일정한 시간(^[1]O(1))이 소요됩니다.키 삽입 및 감소 작업은 상각된 일정한 ^[2]시간에도 작동합니다.요소 삭제(최소 요소를 삭제하는 특수한 경우에 가장 많이 사용됨)는 O(log n) 상각 시간으로 동작합니다.여기서 n은 ^[2]힙의 크기입니다.즉, 빈 데이터 구조에서 시작하여 키 삽입 및 감소 조작과 b 삭제 조작의 시퀀스는 O(a + b log n)의 최악의 경우 시간이 걸립니다.여기서 n은 최대 힙사이즈입니다.바이너리 힙 또는 이항 힙에서 이러한 일련의 연산은 O(a + b) log n) 시간이 걸립니다.따라서 피보나치 힙은 b가 a보다 비정수계수만큼 작을 때 이진 또는 이항 힙보다 낫다.또한 2개의 Fibonacci 힙을 상각된 일정한 시간에 병합하여 이항 힙의 로그 병합 시간을 개선하고 병합을 효율적으로 처리할 수 없는 이진 힙을 개선할 수 있습니다.

priority 큐에 피보나치 힙을 사용하면 다른 느린 priority 큐 데이터 구조를 사용하는 동일한 알고리즘에 비해 그래프에서 두 노드 간의 최단 경로를 계산하는 Dijkstra 알고리즘과 같은 중요한 알고리즘의 점근적 실행 시간이 향상됩니다.

구조.

그림 1피보나치 힙의 예.그것은 0도, 1도, 3도의 세 그루의 나무를 가지고 있다.세 개의 정점이 표시됩니다(파란색으로 표시).따라서 히프의 전위는 9(3 트리 + 2 × (3 마크된 수직)입니다.

피보나치 힙은 최소 히프 속성을 충족하는 트리 집합입니다.즉, 자녀의 키는 항상 부모의 키보다 크거나 같습니다.이는 최소 키가 항상 트리 중 하나의 루트에 있음을 의미합니다.이항 힙에 비해 피보나치 힙의 구조는 더 유연합니다.트리는 정해진 모양을 가지고 있지 않으며 극단적인 경우 힙은 개별 트리의 모든 요소를 가질 수 있습니다.이러한 유연성으로 인해 일부 작업은 느릿느릿 실행되어 이후 작업을 위해 지연될 수 있습니다.예를 들어, 힙을 병합하는 것은 단순히 2개의 트리 리스트를 연결하는 것만으로 이루어지며, 연산 감소 키는 부모로부터 노드를 절단하여 새로운 트리를 형성할 수 있습니다.

단, 원하는 실행시간을 달성하려면 어느 시점에서 히프에 순서를 도입해야 합니다.특히 노드의 도수(여기서 도수는 직계자수를 의미한다)는 상당히 낮은 상태로 유지된다.각 노드는 최대 로그 n의 도수를 가지며, 도수 k의 노드에 뿌리를 둔 서브트리의 크기는 적어도 F이며_k+2, 여기서_k F는 k번째 피보나치 수이다.이것은 각 비루트 노드의 자식을 최대 1명까지 자를 수 있다는 규칙에 의해 실현됩니다.두 번째 아이가 절단되면 노드 자체가 부모로부터 절단되어 새 트리의 루트가 됩니다(아래의 정도 한계 증명 참조).트리가 서로 연결된 최소 삭제 작업에서는 트리 수가 감소합니다.

이완된 구조로 인해 일부 작업은 시간이 오래 걸리는 반면 다른 작업은 매우 빠르게 수행됩니다.상각된 실행 시간 분석에서는 매우 빠른 작업이 실제보다 약간 더 오래 걸린다고 가정하는 잠재적 방법을 사용합니다.이 추가 시간은 나중에 합산되어 저속 동작의 실제 실행 시간에서 차감됩니다.나중에 사용할 수 있도록 절약된 시간은 주어진 순간에 잠재적 함수에 의해 측정됩니다.피보나치 힙의 잠재력은 다음과 같습니다.

전위 = t + 2 m

여기서 t는 피보나치 힙 내의 트리 수, m은 마킹된 노드의 수입니다.노드가 다른 노드의 자식(모든 루트가 표시되지 않음)이 되었기 때문에 노드 중 적어도1개가 절단된 경우 노드가 마킹됩니다.연산의 상각 시간은 실제 시간의 합과 c 곱하기 전위차에 의해 주어집니다.여기서 c는 상수입니다(실시간 동안 O표기의 상수 계수와 일치하도록 선택).

따라서 힙 내의 각 트리의 루트에는 하나의 시간 단위가 저장됩니다.이 시간 단위는 나중에 상각된 시간 0에 이 트리를 다른 트리와 연결하는 데 사용할 수 있습니다.또, 마크 된 각 노드에는, 2개의 시간 단위가 격납되어 있습니다.노드를 부모 노드로부터 절단하기 위해서 사용할 수 있습니다.이 경우 노드는 루트가 되고 두 번째 시간 단위는 다른 루트와 마찬가지로 노드에 저장됩니다.

업무의 실시

빠른 삭제 및 연결을 위해 모든 트리의 루트는 순환 이중 연결 목록을 사용하여 연결됩니다.각 노드의 자식도 이러한 목록을 사용하여 연결됩니다.각 노드에 대해 하위 노드 수와 노드의 표시 여부를 유지합니다.또한 최소 키를 포함하는 루트에 대한 포인터를 유지합니다.

최소값을 포함하는 노드에 대한 포인터를 유지하기 때문에 최소값을 찾는 작업은 이제 단순합니다.힙의 잠재력은 변경되지 않으므로 실제 비용과 상각 비용은 모두 일정합니다.

위에서 언급한 바와 같이, 병합은 두 힙의 트리 루트 목록을 연결하는 것만으로 구현됩니다.이는 일정 시간 내에 수행될 수 있으며 잠재력이 변경되지 않으므로 상각된 시간이 일정해집니다.

삽입 작업은 하나의 요소로 새 힙을 만들고 병합을 수행하는 방식으로 작동합니다.이것은 일정한 시간이 걸리고 나무의 수가 증가하기 때문에 잠재력이 1씩 증가합니다.따라서 상각된 원가는 여전히 일정하다.

작업 추출 최소값(삭제 최소값과 동일)은 3단계로 작동합니다.먼저 최소 요소를 포함하는 루트를 취하여 제거합니다.그것의 아이들은 새로운 나무의 뿌리가 될 것이다.자녀 수가 d일 경우 모든 새로운 루트를 처리하는 데 O(d) 시간이 걸리고 잠재력이 d-1만큼 증가합니다.따라서 이 단계의 상각된 실행 시간은 O(d) = O(log n)입니다.

그러나 최소 추출 작업을 완료하려면 최소 키로 루트에 대한 포인터를 업데이트해야 합니다.유감스럽게도 확인해야 할 루트가 n개까지 있을 수 있습니다.따라서 두 번째 단계에서는 같은 정도의 루트를 연속적으로 연결함으로써 루트의 수를 줄인다.두 개의 루트 u와 v가 같은 차수를 가지면 둘 중 하나를 다른 쪽의 아이로 만들어 키가 작은 쪽이 루트를 유지하도록 합니다.그것의 정도는 1만큼 증가할 것이다.이것은 모든 뿌리가 다른 정도를 가질 때까지 반복됩니다.같은 정도의 나무를 효율적으로 찾기 위해 길이 O(log n)의 배열을 사용합니다. 여기서 각도의 1근에 대한 포인터를 유지합니다.같은 정도의 두 번째 루트가 발견되면 두 루트가 연결되고 배열이 업데이트됩니다.실제 실행 시간은 O(log n + m)입니다.여기서 m은 두 번째 단계 시작의 루트 수입니다.마지막에는 최대 O(log n) 루트가 있습니다(각각의 정도가 다르기 때문입니다).따라서 이 단계 이전부터 이후까지의 전위함수 차이는 O(log n)~m이며, 상각된 실행 시간은 최대 O(log n + m)+c(O(log n)~m)가 됩니다.선택 가능한 c가 충분히 크면 O(log n)로 단순화됩니다.

그림 2최소 추출물 1단계 이후 그림 1의 피보나치 힙.키가 1(최소)인 노드가 삭제되고 해당 노드가 별도의 트리로 추가되었습니다.

그림 3최소 추출 완료 후 그림 1의 피보나치 힙.먼저 노드 3과 노드 6이 서로 연결되어 있습니다.그런 다음 노드 2에 루트된 트리와 결과가 연결됩니다.마지막으로 새로운 최소값이 발견됩니다.

그림 4노드 9의 키를 0으로 낮춘 후 그림 1의 피보나치 힙.이 노드와 표시된 두 개의 상위 노드는 1에 뿌리를 둔 트리에서 잘라낸 후 새 루트로 배치됩니다.

세 번째 단계에서는 나머지 각 루트를 확인하고 최소값을 구합니다.이 작업에는 O(log n) 시간이 걸리고 가능성은 변경되지 않습니다.따라서 추출 최소값의 전체 상각 실행 시간은 O(log n)입니다.

작업 감소 키는 노드를 가져와서 키를 줄입니다.또, 히프 속성이 위반되었을 경우(새로운 키는 부모 키보다 작음), 노드는 부모 키에서 절단됩니다.부모가 루트가 아닌 경우 루트가 표시됩니다.이미 마크가 붙어 있는 경우는, 마찬가지로 잘리고, 부모도 마크가 붙어 있습니다.루트 노드 또는 마크되지 않은 노드에 도달할 때까지 위쪽으로 계속 이동합니다.이제 최소 포인터가 새 최소값인 경우 최소 포인터를 감소된 값으로 설정합니다.그 과정에서 우리는 새로운 나무(예를 들어 k)를 몇 개 만듭니다.첫 번째 트리를 제외한 이 새로운 트리는 각각 원래 마크가 붙어 있었지만 루트로서 마크가 붙어 있지 않습니다.1개의 노드가 마킹될 수 있습니다.따라서 표시된 노드 수는 -(k - 1) + 1 = - k + 2만큼 변화합니다. 이 두 가지 변화를 결합하면 전위는 2µk + 2) + k = -k + 4만큼 변화합니다.절삭을 수행한 실제 시간은 O(k)였으므로 상각된 실행 시간은 일정합니다(또한 c의 선택지가 충분히 넓을 경우, 상각된 실행 시간은 일정합니다.

마지막으로 삭제 대상 요소의 키를 마이너스 무한대로 줄여 힙 전체의 최소로 하는 것만으로 조작 삭제를 실시할 수 있다.그런 다음 추출 최소값을 호출하여 제거합니다.이 작업의 상각된 실행 시간은 O(log n)입니다.

학위 한계 증명

Fibonacci 힙의 상각된 퍼포먼스는 O(log n) 트리 루트의 정도(자녀 수)에 따라 달라집니다.여기서 n은 힙의 크기입니다.여기에서는 힙 내의 임의의 노드x(degree d)에 루트가 있는 (서브)트리의 사이즈가 F 이상이어야_d₊₂ 함을 나타냅니다.F는_k k번째 피보나치 번호입니다.여기서부터 한계치는 ( $d\geq 0$ 에 의해 증명된) 모든 정수 d $d\geq 0$ 0 {\ $\varphi =(1+{\sqrt {5}})/2\doteq 1.618$ d $\geq$ 0 $d\geq 0$ 에 $F_{d+2}\geq \varphi ^{d}$ F $F_{d+2}\geq \varphi ^{d}$ d + $F_{d+2}\geq \varphi ^{d}$ $\varphi =(1+{\sqrt {5}})/2\doteq 1.618$ $\varphi =(1+{\sqrt {5}})/2\doteq 1.618$ $\varphi =(1+{\sqrt {5}})/2\doteq 1.618$ $d+2}\geq \varphi$ ^{ $d}$ 이라는 $F_{d+2}\geq \varphi ^{d}$ $F_{d+2}\geq \varphi ^{d}$ 에 따라 달라집니다.여기서 $\varphi =(1+{\sqrt {5}})/2\doteq 1.618$ ( $\varphi =(1+{\sqrt {5}})/2\doteq 1.618$ 1 + 5 $\varphi =(1+{\sqrt {5}})/2\doteq 1.618$ ) / 2 $\varphi =(1+{\sqrt {5}})/2\doteq 1.618$ 618 1 $\varphi =(1+{\sqrt {5}})/2\doteq 1.618$ （ $display$ style { $varphi = 1$ ））。 $d\$ $+$ 2 $}\geq$ \ $varphi ^{$ d $n\geq F_{d+2}\geq \varphi ^{d}$ 로그를 $d\leq \log _{\varphi }n$ 의 $베이스$ "\displaystyle $\$ $varphi"$ 로 $\varphi$ 가져오면 필요에 따라 $d\leq \log _{\varphi }n$ d $log "\displaystyle$ d $\leq$ \ $log "{\varphi$ } n $d\leq \log _{\varphi }n$ " 가 됩니다.)

힙 내 어딘가에 있는 노드x를 고려합니다(x가 메인트리 중 하나의 루트일 필요는 없습니다).size(x)를 x에 루팅된 트리 크기(x 자체를 포함한 x의 하위 항목 수)로 정의합니다.우리는 x의 높이(x에서 후손 잎까지의 가장 긴 단순한 경로의 길이)에 대한 유도에 의해 그 크기_d₊₂(x) , F를 증명한다. 여기서 d는 x의 정도이다.

베이스 케이스:x의 높이가 0이면 d = 0이고 크기(x) = 1 = F입니다₂.

귀납 케이스:x의 높이와 도수가 양의 d> 0이라고 가정합니다₁. y, y₂, ..., y를_d x의 자녀로 하고, y가 가장 이른 시간₁(y가 가장 늦은 시간_d, y가 가장 늦은 시간) 순으로 인덱스를 붙이고, c₂, c, ..., c를₁_d 각각의 자녀로 합니다.우리는 y가 x의 자녀로 만들어지기 직전에는_i x의₁ 자녀였고_i₋₁, 따라서 x는 적어도 i-1의 학위를 가지고 있었다고_i 주장한다.나무는 뿌리의 각도가 같을 때만 결합되기 때문에 x의 자아가 되었을 때 y도 적어도 i-1의 각도가 있었을_i 것이다.그때부터 지금까지_i y는 (마킹 프로세스에 의해 보증된 바와 같이) 최대 1명의 자아를 잃었을 뿐이므로 현재 c는_i 적어도 i-2이다.이것이 그 주장을 증명한다.

모든 y의_i 높이가 x의 높이보다 엄격히 작기 때문에, 크기(y_i) ≥ F_{c_i}₊₂ f_(i−2)+2 F = F를_i 얻기 위해 귀납 가설을 적용할 수 있습니다.노드 x와₁ y는 각각 크기(x)에 대해 최소 1을 기여하기 때문에 다음과 같이 됩니다.

${textbf {size}(x)\sum _{i=2}^{d}{\textbf {size}(y_{i})\sum _{i}F_{i}=1+\sum _{i=0}^{d}\sum}F_{i}$

루틴 인덕션은 1 $1+\sum _{i=0}^{d}F_{i}=F_{d+2}$ + $1+\sum _{i=0}^{d}F_{i}=F_{d+2}$ i $1+\sum _{i=0}^{d}F_{i}=F_{d+2}$ $1+\sum _{i=0}^{d}F_{i}=F_{d+2}$ $1+\sum _{i=0}^{d}F_{i}=F_{d+2}$ $1+\sum _{i=0}^{d}F_{i}=F_{d+2}$ $1+\sum _{i=0}^{d}F_{i}=F_{d+2}$ $1+\sum _{i=0}^{d}F_{i}=F_{d+2}$ $1+\sum _{i=0}^{d}F_{i}=F_{d+2}$ + $1+\sum _{i=0}^{d}F_{i}=F_{d+2}$ 2 ({ $displaystyle$ 1+\ $sum _{i=$ 0})^{ $d임$ 을 증명합니다.} $임의$ 의 d $00$ (\displaystyle $d\geq$ 0 $d\geq 0$ 에 대해 $F_{$ i}= $F_{d+$ 2 $1+\sum _{i=0}^{d}F_{i}=F_{d+2}$ }. 이 값은 크기(x)에 대한 원하는 하한을 제공합니다 $.$

최악의 경우

Fibonacci 힙은 매우 효율적인 것처럼 보이지만 다음과 같은 ^[3]두 가지 단점이 있습니다.

구현에 관한 한 복잡합니다.
이론적으로 덜 효율적인 더미의 형태에 비해 실제로는 효율적이지 않습니다.가장 간단한 버전에서는 노드당 4개의 포인터를 저장 및 조작해야 하는 반면, 바이너리 힙, 이항 힙, 페어링 힙, Brodal 큐 및 랭킹 페어링 힙과 같은 다른 구조에서는 노드당 2~3개의 포인터만 필요합니다.

빈 구조에서 시작하는 일련의 동작의 총 실행 시간은 위에 제시된 경계에 의해 제한되지만 시퀀스 내의 일부(극소수) 동작은 완료하는 데 매우 오래 걸릴 수 있습니다(특히 삭제 및 삭제 최소 동작은 최악의 경우 선형 실행 시간을 가집니다).이러한 이유로 피보나치 힙 및 기타 상각된 데이터 구조는 실시간 시스템에 적합하지 않을 수 있습니다.Fibonacci 힙이 성능을 상각한 것과 동일한 최악의 성능을 가진 데이터 구조를 생성할 수 있습니다.그러한 구조 중 하나인 Brodal ^[4]큐는 창조자의 말을 빌리자면, "매우 복잡하다"며 "실천에 적용되지 않는다"는 것이다.2012년에 작성된 엄밀한 피보나치^[5] 힙은 Brodal과 같은 최악의 경우 경계를 가진 단순한 구조입니다.구조가 단순하지만 실제로는 엄밀한 피보나치 힙이 복잡한 Brodal 큐보다 느리게 동작하고 기본 피보나치 ^[6]^[7]힙보다 느리게 동작하는 것으로 실험 결과 나타났습니다.Driscell 등의 run-laxed hump는 Marge를 제외한 모든 Fibonacci 힙 조작에 대해 최적의 최악의 성능을 제공합니다.

실행 시간 요약

다음은 다양한 힙 데이터 구조의 시간^[8] 복잡성입니다.함수명은 min-heap을 전제로 합니다."O(f)" 및 "δ(f)"의 의미는 빅 O 표기법을 참조하십시오.

작동	find-min	삭제 최소값	삽입하다	감소 키	혼재
바이너리^[8]	θ(1)	δ(로그 n)	O(log n)	O(log n)	θ(n)
좌파	θ(1)	δ(로그 n)	δ(로그 n)	O(log n)	δ(로그 n)
이항^[8]^[9]	θ(1)	δ(로그 n)	θ(1)^[a]	δ(로그 n)	O(log n)^[b]
피보나치^[8]^[2]	θ(1)	O(log n)^[a]	θ(1)	θ(1)^[a]	θ(1)
페어링^[10]	θ(1)	O(log n)^[a]	θ(1)	o(로그 n)^[a]^[c]	θ(1)
브로달^[13]^[d]	θ(1)	O(log n)	θ(1)	θ(1)	θ(1)
랭크 페어링^[15]	θ(1)	O(log n)^[a]	θ(1)	θ(1)^[a]	θ(1)
엄밀한 피보나치^[16]	θ(1)	O(log n)	θ(1)	θ(1)	θ(1)
2 ~ 3 히프^[17]	O(log n)	O(log n)^[a]	O(log n)^[a]	θ(1)	?

^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ 상각시간
^ n은 큰 힙의 크기입니다.
^ 하한 $\Omega (\log \log n),$ ( $\Omega (\log \log n),$ log $\Omega (\log \log n),$ n $\Omega (\log \log n),$ ) $\Omega (\log \log n),$ , {\ $displaystyle \Omega$ ( \ $log \log$ n ) $\Omega (\log \log n),$ $O(2^{2{\sqrt {\log \log n}}}).$ O의 $\Omega (\log \log n),$ ^[11] $O(2^{2{\sqrt {\log \log n}}}).$ ( $O(2^{2{\sqrt {\log \log n}}}).$ $O(2^{2{\sqrt {\log \log n}}}).$ $O(2^{2{\sqrt {\log \log n}}}).$ log $O(2^{2{\sqrt {\log \log n}}}).$ n ) $。{$ $display style$ O ( $2$ ^ { $2$ \ $sq$ \ $log$ \ $log n$ } } 。 $}$ ^[12]
^ Brodal과 Okasaki는 나중에 지원되지 않는 decrement-key를 제외하고 동일한 경계를 가진 영속적인 변종을 기술합니다.n개의 요소가 있는 힙은 O(n)^[14]에서 상향식으로 구성할 수 있습니다.

실제 고려 사항

피보나치 힙은 노드당 메모리 소비량이 크고 모든 작업에서 일정한 요인이 높기 때문에 실제로는 속도가^[18] 느리다는 평판이 있습니다.최근 실험 결과에 따르면 피보나치 힙은 지진 힙, 위반 힙, 엄격한 피보나치 힙, 순위 쌍 힙 등 대부분의 후속 파생 모델에 비해 실제로 더 효율적이지만 쌍 힙 또는 어레이 기반 ^[7]힙보다는 덜 효율적입니다.

레퍼런스

^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Chapter 20: Fibonacci Heaps". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 476–497. ISBN 0-262-03293-7. 제3판 518쪽
^ ^a ^b ^c Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF). Journal of the Association for Computing Machinery. 34 (3): 596–615. CiteSeerX 10.1.1.309.8927. doi:10.1145/28869.28874.
^ Fredman, Michael L.; Sedgewick, Robert; Sleator, Daniel D.; Tarjan, Robert E. (1986). "The pairing heap: a new form of self-adjusting heap" (PDF). Algorithmica. 1 (1–4): 111–129. doi:10.1007/BF01840439. S2CID 23664143.
^ Gerth Stølting Brodal (1996), "Worst-Case Efficient Priority Queues", Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics: 52–58, CiteSeerX 10.1.1.43.8133, ISBN 0-89871-366-8
^ Brodal, G. S. L.; Lagogiannis, G.; Tarjan, R. E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. p. 1177. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.
^ Mrena, Michal; Sedlacek, Peter; Kvassay, Miroslav (June 2019). "Practical Applicability of Advanced Implementations of Priority Queues in Finding Shortest Paths". 2019 International Conference on Information and Digital Technologies (IDT). Zilina, Slovakia: IEEE: 335–344. doi:10.1109/DT.2019.8813457. ISBN 9781728114019. S2CID 201812705.
^ ^a ^b Larkin, Daniel; Sen, Siddhartha; Tarjan, Robert (2014). "A Back-to-Basics Empirical Study of Priority Queues". Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments: 61–72. arXiv:1403.0252. Bibcode:2014arXiv1403.0252L. doi:10.1137/1.9781611973198.7. ISBN 978-1-61197-319-8. S2CID 15216766.
^ ^a ^b ^c ^d Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
^ "Binomial Heap Brilliant Math & Science Wiki". brilliant.org. Retrieved 2019-09-30.
^ Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77, arXiv:1110.4428, CiteSeerX 10.1.1.748.7812, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2
^ Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures" (PDF). Journal of the Association for Computing Machinery. 46 (4): 473–501. doi:10.1145/320211.320214.
^ Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. CiteSeerX 10.1.1.549.471. doi:10.1109/SFCS.2005.75. ISBN 0-7695-2468-0.
^ Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
^ Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338–341. ISBN 0-471-46983-1.
^ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.
^ Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184. CiteSeerX 10.1.1.233.1740. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.
^ Takaoka, Tadao (1999), Theory of 2–3 Heaps (PDF), p. 12
^ http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/FibonacciHeaps.pdf, 페이지 79

외부 링크

[amortized-10] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ 상각시간

[meld-11] 은 큰 힙의 크기입니다.

[pairingdecreasekey-15] 하한 $\Omega (\log \log n),$ ( $\Omega (\log \log n),$ log $\Omega (\log \log n),$ n $\Omega (\log \log n),$ ) $\Omega (\log \log n),$ , {\ $displaystyle \Omega$ ( \ $log \log$ n ) $\Omega (\log \log n),$ $O(2^{2{\sqrt {\log \log n}}}).$ O의 $\Omega (\log \log n),$ ^[11] $O(2^{2{\sqrt {\log \log n}}}).$ ( $O(2^{2{\sqrt {\log \log n}}}).$ $O(2^{2{\sqrt {\log \log n}}}).$ $O(2^{2{\sqrt {\log \log n}}}).$ log $O(2^{2{\sqrt {\log \log n}}}).$ n ) $。{$ $display style$ O ( $2$ ^ { $2$ \ $sq$ \ $log$ \ $log n$ } } 。 $}$ ^[12]

[brodal-18] Brodal과 Okasaki는 나중에 지원되지 않는 decrement-key를 제외하고 동일한 경계를 가진 영속적인 변종을 기술합니다.n개의 요소가 있는 힙은 O(n)^[14]에서 상향식으로 구성할 수 있습니다.

[1] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Chapter 20: Fibonacci Heaps". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 476–497. ISBN 0-262-03293-7. 제3판 518쪽

[Fredman_And_Tarjan-2] Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF). Journal of the Association for Computing Machinery. 34 (3): 596–615. CiteSeerX 10.1.1.309.8927. doi:10.1145/28869.28874.

[FSST-3] Fredman, Michael L.; Sedgewick, Robert; Sleator, Daniel D.; Tarjan, Robert E. (1986). "The pairing heap: a new form of self-adjusting heap" (PDF). Algorithmica. 1 (1–4): 111–129. doi:10.1007/BF01840439. S2CID 23664143.

[bare_url-4] Gerth Stølting Brodal (1996), "Worst-Case Efficient Priority Queues", Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics: 52–58, CiteSeerX 10.1.1.43.8133, ISBN 0-89871-366-8

[5] Brodal, G. S. L.; Lagogiannis, G.; Tarjan, R. E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. p. 1177. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.

[6] Mrena, Michal; Sedlacek, Peter; Kvassay, Miroslav (June 2019). "Practical Applicability of Advanced Implementations of Priority Queues in Finding Shortest Paths". 2019 International Conference on Information and Digital Technologies (IDT). Zilina, Slovakia: IEEE: 335–344. doi:10.1109/DT.2019.8813457. ISBN 9781728114019. S2CID 201812705.

[:0-7] Larkin, Daniel; Sen, Siddhartha; Tarjan, Robert (2014). "A Back-to-Basics Empirical Study of Priority Queues". Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments: 61–72. arXiv:1403.0252. Bibcode:2014arXiv1403.0252L. doi:10.1137/1.9781611973198.7. ISBN 978-1-61197-319-8. S2CID 15216766.

[CLRS-8] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.

[9] "Binomial Heap Brilliant Math & Science Wiki". brilliant.org. Retrieved 2019-09-30.

[Iacono-12] Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77, arXiv:1110.4428, CiteSeerX 10.1.1.748.7812, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2

[Fredman1999-13] Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures" (PDF). Journal of the Association for Computing Machinery. 46 (4): 473–501. doi:10.1145/320211.320214.

[14] Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. CiteSeerX 10.1.1.549.471. doi:10.1109/SFCS.2005.75. ISBN 0-7695-2468-0.

[16] Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58

[17] Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338–341. ISBN 0-471-46983-1.

[19] Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.

[20] Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184. CiteSeerX 10.1.1.233.1740. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.

[21] Takaoka, Tadao (1999), Theory of 2–3 Heaps (PDF), p. 12

[22] ttp://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/FibonacciHeaps.pdf, 페이지 79

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[a]

[b]

[10]

[c]

[13]

[d]

[15]

[16]

[17]

[11]

[12]

[14]

[18]

v t 잘 알려진 데이터 구조
종류들	수집 컨테이너.
추상적인	연관 배열 멀티맵 데이터 구조 검색 목록. 스택 큐 더블 엔드 큐 priority 큐 이중 엔드 priority 큐 세트 멀티셋 디조인트 세트
어레이	비트 배열 순환 버퍼 다이내믹 어레이 해시 테이블 해시 어레이 트리 희박 행렬
링크되어 있다	어소시에이션리스트 링크 리스트 스킵 리스트 언롤링된 링크 리스트 XOR 링크 리스트
나무들	B-트리 이진 검색 트리 AA나무 AVL 트리 붉은색-검은색 셀프밸런싱 트리 스플레이 트리 히프 이진 힙 이항 힙 피보나치 힙 R 트리 R* 트리 R+ 트리 힐베르트 R-트리 트리 해시 트리
그래프	이항 결정도 방향 비순환 그래프 지시 비순환 단어 그래프
데이터 구조 목록

Search