FAV-ZCU/KIV PPA2/15. ADT Prioritní fronta.md

Prioritní fronta

• abstraktní datový typ

Žravé (greedy) algoritmy

• zváží všechny možnosti pro další krok
  • přiřadí cenu
• provede krok s nejlepší (největší/nejmenší) cenou

• mohou ale nemusí vést k optimálnímu řešení
  • suboptimální: doručování balíků (body, kam musím doručit, ale chci ujet co nejméně km)
    • může sloužit jako heuristika
  • optimální: minimální kostra grafu
    • spojení měst do jedné počítačové sítě
    • graf: města a možná spojení
    • potřeba najít podmnožinu spojující všechna města a mající nejmenší možnou sumu ohodnocení
    • řešení: najdeme nejkratší nezpracovanou hranu
      • zkontrolujeme, zda přidáním nevznikne cyklus - jestli ne, přidáme
      • vznikne optimální řešení

• Dijkstrův algoritmus
  • nejkratší cesta v ohodnoceném grafu
  • vrcholům přiřazuje dočasné ohodnocení
  • z dočasně ohodnocených vybere ten s nejnižším ohodnocením
  • okolním vrcholům se aktualizuje hodnocení

• klíčový problém
  • najít v množině dalších možných kroků ten s nejmenší/největší cenou

• obecný žravý algoritmus
  • celkem přidá n prvků
  • celkem odebere n prvků
  • obecné pořadí přidávání/odebírání

Operace

• přidání prvku (hodnota, priorita)
• zjištění nejmenšího/největšího prvku (z hlediska priority)
• odebrání nejmenšího/největšího prvku (z hlediska priority)
• aktualizace priority prvku

• oproti BST některé operace nevyžadujeme
  • vypsání všech prvků v pořadí klíčů (priorit)
  • zjištění, zda obsahuje prvek s klíčem (prioritou)
  • odebrání libovolného prvku

Možnosti implementace

• triviální: dynamickým seřazeným polem
  • odebírání rychlé
  • přidávání pomalé: \Omega(n^2)
• binární vyhledávácí strom (klíčem priorita)
• halda
  • datová struktura
  • speciální binární strom vytvořený z priorit
  • vlastnosti haldy
    • úplný binární strom
    • priorita ve vrcholu je vždy větší než priorita potomků
  • po každé operaci je potřeba obnovit vlastnosti haldy

Implementace

• uchováváme int[] values, int[] priorities a int count
• změna priority hodnoty value
  • nevíme, kde je
  • musíme to evidovat
    • HashMap<ValueType, Integer> position

Složitost

• binární strom je před každou operací úplný
• hlouba rekurze je maximálně h
• složitost přidání a odebrání je \Omega(\log_{2}(n))
• obecný žravý algoritmus má složitost \mathcal O(n \log(n))

Řazení haldou (Heap sort)

• založíme prázdnou haldu
• přidáme postupně všechny prvky
• postupně odebereme n-krát největší prvek
• celkem: \mathcal O(n \log(n))

• vnitřní řazení haldou
  • haldu umístíme na uvolněná místa pole
• urychlení vytváření haldy
  • budeme je vytvářet od konce stromu (od listů)

• složitost
  • nejhorší a očekávaná: \Theta(n \log(n))
  • paměťová: \Theta(1)