Brodalská fronta - Brodal queue

v počítačová věda, Brodalská fronta je halda /prioritní fronta struktura s velmi nízkou nejhorší případ časové hranice: pro vložení, find-minimum, meld (sloučit dvě fronty) a snížit klíč a pro odstranění - minimální a obecné odstranění. Jsou první hromadnou variantou, která těchto hranic dosáhla, aniž by se uchýlila k amortizaci provozních nákladů. Brodalské fronty jsou pojmenovány podle jejich vynálezce Gerth Stølting Brodal.[1]

I když mají lepší asymptotické hranice než jiné struktury prioritních front, jsou, slovy samotného Brodala, „docela komplikované“ a „[ne] použitelné v praxi“.[1] Brodal a Okasaki popsat a vytrvalý (čistě funkční ) verze fronty Brodal.[2]

Shrnutí provozních časů

Tady jsou časové složitosti[3] různých haldy datových struktur. Názvy funkcí předpokládají minimální hromadu. Ve smyslu „Ó(F)" a "Θ(F) „viz Velká O notace.

Úkonnajít-minvymazat-minvložitzmenšovací klíčsplynout
Binární[3]Θ(1)Θ(logn)Ó(logn)Ó(logn)Θ(n)
LevicovýΘ(1)Θ(log n)Θ(log n)Ó(log n)Θ(log n)
Binomický[3][4]Θ(1)Θ(log n)Θ(1)[A]Θ(log n)Ó(logn)[b]
Fibonacci[3][5]Θ(1)Ó(logn)[A]Θ(1)Θ(1)[A]Θ(1)
Párování[6]Θ(1)Ó(log n)[A]Θ(1)Ó(logn)[A][C]Θ(1)
Brodal[9][d]Θ(1)Ó(logn)Θ(1)Θ(1)Θ(1)
Hodnostní párování[11]Θ(1)Ó(log n)[A]Θ(1)Θ(1)[A]Θ(1)
Přísný Fibonacci[12]Θ(1)Ó(log n)Θ(1)Θ(1)Θ(1)
2–3 hromada[13]Ó(log n)Ó(log n)[A]Ó(log n)[A]Θ(1)?
  1. ^ A b C d E F G h i Amortizovaný čas.
  2. ^ n je velikost větší hromady.
  3. ^ Dolní hranice [7] horní hranice [8]
  4. ^ Brodal a Okasaki později popisují a vytrvalý varianta se stejnými mezemi s výjimkou redukčního klíče, který není podporován n prvky lze konstruovat zdola nahoru Ó(n).[10]

Reference

  1. ^ A b Gerth Stølting Brodal (1996). Nejhorší efektivní prioritní fronty. Proc. 7. ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
  2. ^ Gerth Stølting Brodal a Chris Okasaki (1996). Optimální čistě funkční prioritní fronty. Journal of Functional Programming.
  3. ^ A b C d Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Úvod do algoritmů (1. vyd.). MIT Press a McGraw-Hill. ISBN  0-262-03141-8.
  4. ^ "Binomická halda | Brilliant Math & Science Wiki". brilliant.org. Citováno 2019-09-30.
  5. ^ Fredman, Michael Lawrence; Tarjan, Robert E. (Červenec 1987). „Fibonacciho hromady a jejich použití ve vylepšených algoritmech optimalizace sítě“ (PDF). Časopis Asociace pro výpočetní techniku. 34 (3): 596–615. CiteSeerX  10.1.1.309.8927. doi:10.1145/28869.28874.
  6. ^ Iacono, Johne (2000), „Vylepšené horní hranice pro párování hromad“, Proc. 7. skandinávský seminář o teorii algoritmu (PDF), Přednášky v informatice, 1851, Springer-Verlag, str. 63–77, arXiv:1110.4428, CiteSeerX  10.1.1.748.7812, doi:10.1007 / 3-540-44985-X_5, ISBN  3-540-67690-2
  7. ^ Fredman, Michael Lawrence (Červenec 1999). „O efektivitě párování hromad a souvisejících datových struktur“ (PDF). Časopis Asociace pro výpočetní techniku. 46 (4): 473–501. doi:10.1145/320211.320214.
  8. ^ Pettie, Seth (2005). Směrem ke konečné analýze párování hromad (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. 174–183. CiteSeerX  10.1.1.549.471. doi:10.1109 / SFCS.2005.75. ISBN  0-7695-2468-0.
  9. ^ Brodal, Gerth S. (1996), „Nejhorší efektivní fronty priorit“ (PDF), Proc. 7. ročník sympozia ACM-SIAM o diskrétních algoritmech, str. 52–58
  10. ^ Goodrich, Michael T.; Tamassia, Roberto (2004). „7.3.6. Konstrukce haldy zdola nahoru“. Datové struktury a algoritmy v Javě (3. vyd.). 338–341. ISBN  0-471-46983-1.
  11. ^ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (Listopad 2011). „Hromadné párování“ (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.
  12. ^ Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Přísné hromady Fibonacci (PDF). Sborník 44. sympozia o teorii práce na počítači - STOC '12. str. 1177–1184. CiteSeerX  10.1.1.233.1740. doi:10.1145/2213977.2214082. ISBN  978-1-4503-1245-5.
  13. ^ Takaoka, Tadao (1999), Teorie 2–3 hromád (PDF), str. 12