Prioritní fronta
Z FAV wiki
(Rozdíly mezi verzemi)
(Založena nová stránka: Speciální prípad ADT podobne jako zásobník a fronta, výber odebere prvek s nejvyšší ci nejnižší prioritou (maximová resp. minimová PF) Vkládat lze prvky s li...) |
m (kategorizace) |
||
| (Nejsou zobrazeny 2 mezilehlé verze od 1 uživatele.) | |||
| Řádka 1: | Řádka 1: | ||
| − | Speciální | + | Speciální případ ADT podobne jako zásobník a fronta, výběr odebere prvek s nejvyšší či nejnižší prioritou (maximová resp. minimová PF) Vkládat lze prvky s libovolnou prioritou. |
| − | Implementace polem / spoj.seznamem | + | |
| − | Složitost podle přístupu: | + | '''Implementace:''' polem / spoj.seznamem |
| + | |||
| + | |||
| + | == Složitost podle přístupu: == | ||
Rozhraní | Rozhraní | ||
| − | vytvoření | + | * vytvoření prázdný fronty |
| − | test | + | * test prázdné fronty |
| − | vložení a výběr prvku | + | * vložení a výběr prvku |
| − | Lazy: | + | '''Lazy:''' |
Pole či seznam je neuspořádaný, vkládáme prvek vždy na konec v poli (O(1)) a na začátek v seznamu (O(1)). Při výběru musíme najít maximum, v obou případech O(n) | Pole či seznam je neuspořádaný, vkládáme prvek vždy na konec v poli (O(1)) a na začátek v seznamu (O(1)). Při výběru musíme najít maximum, v obou případech O(n) | ||
| − | Eager: | + | |
| + | '''Eager:''' | ||
Pole či seznam je uspořádaný, prvek vkládáme tak, aby byla struktura seřazena. Vložení je O(n), ale výběr je O(1) (ze začátku seznamu / konce pole) | Pole či seznam je uspořádaný, prvek vkládáme tak, aby byla struktura seřazena. Vložení je O(n), ale výběr je O(1) (ze začátku seznamu / konce pole) | ||
| − | Kombinace: | + | |
| + | '''Kombinace:''' | ||
Implementace pomocí BVS nebo haldy - vložení i výber O(log2n) | Implementace pomocí BVS nebo haldy - vložení i výber O(log2n) | ||
| − | Modifikovatelná prioritní fronta | + | |
| + | == Modifikovatelná prioritní fronta == | ||
| + | |||
Pomocí haldy, a | Pomocí haldy, a | ||
| − | + | # přidáme mapu prvek->pozice v haldě. Změnou priority a obnovením haldy je možné v O(log2n) prioritu i měnit | |
| − | + | # bez mapy je hledání prvku v haldě další O(log2n) čas, celkem tedy hledání O(log2n) + obnovení haldy O(log2n) | |
Pokud proritu příliš neměníme, způsob 1 je výhodnější, ale paměťově náročnější | Pokud proritu příliš neměníme, způsob 1 je výhodnější, ale paměťově náročnější | ||
| + | |||
| + | {{fav-kiv-bzinf}} | ||
| + | [[Kategorie:fav-kiv-bzinf]] | ||
Aktuální verze z 20. 2. 2014, 06:35
Speciální případ ADT podobne jako zásobník a fronta, výběr odebere prvek s nejvyšší či nejnižší prioritou (maximová resp. minimová PF) Vkládat lze prvky s libovolnou prioritou.
Implementace: polem / spoj.seznamem
[editovat] Složitost podle přístupu:
Rozhraní
- vytvoření prázdný fronty
- test prázdné fronty
- vložení a výběr prvku
Lazy: Pole či seznam je neuspořádaný, vkládáme prvek vždy na konec v poli (O(1)) a na začátek v seznamu (O(1)). Při výběru musíme najít maximum, v obou případech O(n)
Eager: Pole či seznam je uspořádaný, prvek vkládáme tak, aby byla struktura seřazena. Vložení je O(n), ale výběr je O(1) (ze začátku seznamu / konce pole)
Kombinace: Implementace pomocí BVS nebo haldy - vložení i výber O(log2n)
[editovat] Modifikovatelná prioritní fronta
Pomocí haldy, a
- přidáme mapu prvek->pozice v haldě. Změnou priority a obnovením haldy je možné v O(log2n) prioritu i měnit
- bez mapy je hledání prvku v haldě další O(log2n) čas, celkem tedy hledání O(log2n) + obnovení haldy O(log2n)
Pokud proritu příliš neměníme, způsob 1 je výhodnější, ale paměťově náročnější
