브로달 줄

컴퓨터 과학에서 브로달 대기열은 최악의 경우 시간 범위가 $O(1)$ 낮은 힙/우선순위 대기열 구조로, 삽입 $,$ 찾기 최소, 멜드(두 개의 대기열) 및 감소키 $O(\mathrm {log} (n))$ $O(\mathrm {log} (n))$ g $O(\mathrm {log} (n))$ ) ${\displaystyle O(\mathrm {log})(n)$ 는 삭제 최소값 및 일반 삭제를 위한 $O(\mathrm {log} (n))$ $O(\mathrm {log} (n))$ $O(1)$ O $)$ 이다.그들은 운영비 상각에 의존하지 않고 이러한 한도를 달성한 최초의 힙 변종이다.브로달 큐는 발명가 게르트 스톨팅 브로달의 이름을 따서 지어졌다.^[1]

다른 우선순위 대기열 구조보다 점근성이 뛰어난 반면, 브로달 자신은 "정밀한 복잡함"과 "실제로 적용할 수 없음"^[1]이라고 말한다.브로달과 오카사키에는 브로달 큐의 지속적(순수하게 기능적인) 버전이 묘사되어 있다.^[2]

실행 시간 요약

여기 다양한 힙 데이터 구조의 시간 복잡성이^[3] 있다.함수 이름은 최소 히프를 가정한다."O(f)"와 "θ(f)"의 의미는 빅 O 표기법을 참조하십시오.

작전	소인을 찾아내다	삭제민	삽입하다	줄임말	섞다
이진수^[3]	Θ(1)	θ(log n)	O(log n)	O(log n)	θ(n)
좌익	Θ(1)	θ(log n)	θ(log n)	O(log n)	θ(log n)
이항체^[3]^[4]	Θ(1)	θ(log n)	Θ(1)^[a]	θ(log n)	O(log n)^[b]
피보나치^[3]^[5]	Θ(1)	O(log n)^[a]	Θ(1)	Θ(1)^[a]	Θ(1)
페어링^[6]	Θ(1)	O(log n)^[a]	Θ(1)	o(log n)^[a]^[c]	Θ(1)
브로달^[9]^[d]	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
랭크페어링^[11]	Θ(1)	O(log n)^[a]	Θ(1)	Θ(1)^[a]	Θ(1)
엄격한 피보나치^[12]	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
2-3 힙^[13]	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),$ $\Omega (\log \log n),$ ) $\Omega (\log \log n),$ , $\Oomega(\log \log n),$ $O(2^{2{\sqrt {\log \log n}}}).$ 의 상한 $\Omega (\log \log n),$ ^[7] $O(2^{2{\sqrt {\log \log n}}}).$ 2 $O(2^{2{\sqrt {\log \log n}}}).$ $O(2^{2{\sqrt {\log \log n}}}).$ n ) $O(2^{2{\sqrt {\log \log n}}}).$ . ${\displaystyle O(2^{\sqrt$ {\sqrt ${\log n}}).$ $}$ ^[8]
^ 브로달과 오카사키에서는 나중에 지원되지 않는 감소키를 제외하고 같은 경계를 가진 지속 변종을 기술한다.원소가 n개인 힙은 O(n)에 상향으로 시공할 수 있다.^[10]

참조

^ ^a ^b 게르트 스톨팅 브로달(1996년).최악의 경우 효율적인 우선 순위 대기열.Proc. 제7회 ACM-SIAM 이산 알고리즘 심포지엄, 페이지 52-58
^ 게르트 스톨팅 브로달과 크리스 오카사키(1996년).최적의 순기능 우선 순위 대기열.기능 프로그래밍 저널.
^ ^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.
^ 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.
^ 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

이 알고리즘이나 데이터 구조와 관련된 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.

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

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

[pairingdecreasekey-11] $\Omega (\log \log n),$ 의 하한 $\Omega (\log \log n),$ log $\Omega (\log \log n),$ $\Omega (\log \log n),$ ) $\Omega (\log \log n),$ , $\Oomega(\log \log n),$ $O(2^{2{\sqrt {\log \log n}}}).$ 의 상한 $\Omega (\log \log n),$ ^[7] $O(2^{2{\sqrt {\log \log n}}}).$ 2 $O(2^{2{\sqrt {\log \log n}}}).$ $O(2^{2{\sqrt {\log \log n}}}).$ n ) $O(2^{2{\sqrt {\log \log n}}}).$ . ${\displaystyle O(2^{\sqrt$ {\sqrt ${\log n}}).$ $}$ ^[8]

[brodal-14] 브로달과 오카사키에서는 나중에 지원되지 않는 감소키를 제외하고 같은 경계를 가진 지속 변종을 기술한다.원소가 n개인 힙은 O(n)에 상향으로 시공할 수 있다.^[10]

[Brodal-1] 게르트 스톨팅 브로달(1996년).최악의 경우 효율적인 우선 순위 대기열.Proc. 제7회 ACM-SIAM 이산 알고리즘 심포지엄, 페이지 52-58

[BrodalOkasaki-2] 게르트 스톨팅 브로달과 크리스 오카사키(1996년).최적의 순기능 우선 순위 대기열.기능 프로그래밍 저널.

[CLRS-3] 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.

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

[Fredman_And_Tarjan-7] 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.

[Iacono-8] 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-9] 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.

[10] 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.

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

[13] 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.

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

[16] 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.

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

[1]

[2]

[3]

[4]

[a]

[b]

[5]

[6]

[c]

[9]

[d]

[11]

[12]

[13]

[7]

[8]

[10]

Search

브로달 줄

네임스페이스

더

실행 시간 요약

참조