Kolejka Brodala
W informatyce kolejka Brodala to struktura sterty / kolejki priorytetowej bardzo niskimi najgorszymi ograniczeniami czasowymi : do , znajdowania minimum, łączenia (połączenia dwóch kolejek i _ Są pierwszym wariantem hałdy, który osiągnął te granice bez uciekania się do amortyzacji kosztów operacyjnych. Kolejki Brodal zostały nazwane na cześć ich wynalazcy Gertha Støltinga Brodala .
Chociaż mają lepsze granice asymptotyczne niż inne struktury kolejek priorytetowych, są one, jak mówi sam Brodal, „dość skomplikowane” i „[nie] mają zastosowania w praktyce”. Brodal i Okasaki opisują trwałą ( czysto funkcjonalną ) wersję kolejek Brodal.
Podsumowanie czasów biegu
Oto złożoność czasowa różnych struktur danych sterty. Nazwy funkcji zakładają min-stertę. Znaczenie „ O ( f )” i „ Θ ( f )” można znaleźć w notacji Big O.
| Operacja | znajdź min | usuń min | wstawić | klawisz zmniejszania | stopić |
|---|---|---|---|---|---|
| Dwójkowy | Θ (1) | Θ (log n ) | O (log n ) | O (log n ) | Θ ( n ) |
| Lewicowy | Θ (1) | Θ (log n ) | Θ (log n ) | O (log n ) | Θ (log n ) |
| Dwumianowy | Θ (1) | Θ (log n ) | Θ (1) | Θ (log n ) | O (log n ) |
| Fibonacciego | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| Łączenie w pary | Θ (1) | O (log n ) | Θ (1) | o (log n ) | Θ (1) |
| Brodal | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| Parowanie rang | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| Ścisłe Fibonacciego | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| 2–3 sterty | O (log n ) | O (log n ) | O (log n ) | Θ (1) | ? |
- ^ ab . Gerth Stølting Brodal (1996) W najgorszym przypadku wydajne kolejki priorytetowe. proc. 7. Sympozjum ACM-SIAM na temat algorytmów dyskretnych, s. 52–58
- ^ Gerth Stølting Brodal i Chris Okasaki (1996). Optymalne czysto funkcjonalne kolejki priorytetowe . Dziennik programowania funkcjonalnego .
- ^ abcd Cormen , Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. (1990). Wprowadzenie do algorytmów (wyd. 1). MIT Press i McGraw-Hill. ISBN 0-262-03141-8 .
- Bibliografia Linki genialny.org . Źródło 2019-09-30 . zewnętrzne
- Bibliografia _ _ Tarjan, Robert E. (lipiec 1987). „Handry Fibonacciego i ich zastosowania w ulepszonych algorytmach optymalizacji sieci” (PDF) . Dziennik Stowarzyszenia Maszyn Komputerowych . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . doi : 10.1145/28869.28874 .
- ^ Iacono, John (2000), „Ulepszone górne granice parowania stosów”, Proc. 7. skandynawskie warsztaty z teorii algorytmów (PDF) , notatki z wykładów z informatyki, tom. 1851, Springer-Verlag, s. 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 (lipiec 1999). „O wydajności stosów parowania i powiązanych struktur danych” (PDF) . Dziennik Stowarzyszenia Maszyn Komputerowych . 46 (4): 473–501. doi : 10.1145/320211.320214 .
- ^ Pettie, Seth (2005). W kierunku ostatecznej analizy stert parowania (PDF) . FOCS '05 Materiały z 46. dorocznego sympozjum IEEE na temat podstaw informatyki. s. 174–183. CiteSeerX 10.1.1.549.471 . doi : 10.1109/SFCS.2005.75 . ISBN 0-7695-2468-0 .
- ^ Brodal, Gerth S. (1996), „Wydajne kolejki priorytetowe w najgorszym przypadku” (PDF) , Proc. 7. doroczne sympozjum ACM-SIAM na temat algorytmów dyskretnych , s. 52–58
- ^ Goodrich, Michael T .; Tamassia, Roberto (2004). „7.3.6. Budowa sterty oddolnej”. Struktury danych i algorytmy w Javie (wyd. 3). s. 338–341. ISBN 0-471-46983-1 .
- ^ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (listopad 2011). „Stosy parowania rang” (PDF) . SIAM J. Informatyka . 40 (6): 1463–1485. doi : 10.1137/100785351 .
- ^ Brodal, Gerth Stølting ; Lagogiannis, George; Tarjan, Robert E. (2012). Ścisłe stosy Fibonacciego (PDF) . Materiały z 44. sympozjum Teorii Informatyki - STOC '12. s. 1177–1184. CiteSeerX 10.1.1.233.1740 . doi : 10.1145/2213977.2214082 . ISBN 978-1-4503-1245-5 .
- ^ Takaoka, Tadao (1999), Teoria 2–3 hałd (PDF) , s. 12