12 - Spojové struktury a ADT

• Abstraktní datové typy - konkrétněji prioritní fronta
• Implementace prioritní fronty
• Písemný test

V tomto cvičení se kromě psaní testu budeme věnovat abstraktním datovým typům (ADT). V předešlých cvičeních jste se seznámili například s frontou a zásobníkem.

Dnes si ukážeme abstraktní datový typ prioritní fronta. Vyzkoušíme si základní implementaci prioritní fronty lineárním vyhledáváním.

V domácím úkolu pak budeme implementovat prioritní frontu binární haldou.

Jak jste již v tomto semestru zjistili, je třeba dobře plánovat svůj čas, abyste dostáli svým povinostem.

Jakmile máme úkolů mnoho, tak se hodí nějaký úkolníček nebo chcete-li ToDoList.

Úkoly si můžeme ukládat do fronty. Jistě jste již slyšeli, že fronta je tzv. FIFO, co to znamená? V jakém pořadí budeme úkoly z fronty odebírat?

Jednotlivé úkoly mají svoji prioritu. Ač je určení si priorit v tomto případě stěžejní, my se určením priorit v PR1 nebudeme zatěžovat. Předpokládejme, že priority jsou určeny. Nyní je potřeba úkoly zpracovat v pořadí podle priority - samozřejmě od nejvyšší priority!

Mohli bychom úkoly ve frontě seřadit. Úkoly ale obvykle přibývají dříve než stihneme všechny předchozí zpracovat (http://9gag.com/gag/aQqLVK8). Seřadit frontu po přidání nového prvku je možné, ale tento přístup pak z každého přidání prvku dělá výpočetně náročnou operaci.

Ukážeme si k čemu by nám mohl být abstraktní datový typ prioritní fronta. Zkusíme si, že prioritní frontu můžeme implementovat různými způsoby. A ne všechny způsoby budou stejně efektivní.

1. Stáhneme a spustíme si připravený projekt pr1-lab12.zip.
2. Metoda run ve třídě Simulator přijímá parametr tasks. Jakého typu může být tento parametr? Vysvětlete, proč můžeme z Lab12.main volat metodu run se současnými parametry typu ArrayQueue, LinkedList a PriorityQueue.
3. Podívejme se na rozhraní fronty (interface Queue). Vysvětlete jednotlivé operace.
4. V čem se liší prioritní fronta od “klasické” fronty? Podívejme se na PriorityQueue interface. Jak bychom chtěli, aby vypadal výstup při použití prioritní fronty?
5. Implementujte Comparator, tak aby platil popis metody compare (cz.cvut.fel.pr1.provided.Comparator.java).
6. Doimplementujte ArrayPriorityQueue. Můžete použít metodu remove definovanou v ArrayQueue. (Pokud si nevíte rady, můžete se podívat do LListPriorityQueue, kde je také fronta rozšířena na prioritní ale s využitím spojového seznamu.)
7. Vyzkoušejte implementace porovnat s různým počtem úkolů (Task).

int initTaskCount = 10000;
boolean verbose = false;

lab12