====== 12 - Spojové struktury a ADT ======
<note important>Bude upřesněno</note>

===== Náplň cvičení =====

  * 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.

===== ToDoList =====

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í.


=== Úkoly: ===

  - Stáhneme a spustíme si připravený projekt {{courses:A0B36PR1:tutorials:12:pr1-lab12.zip|}}. 
  - 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//.   
  - Podívejme se na rozhraní fronty (interface Queue). Vysvětlete jednotlivé operace.
  - 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?
  - Implementujte //Comparator//, tak aby platil popis metody //compare// (cz.cvut.fel.pr1.provided.Comparator.java).
  - 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.) 
  - Vyzkoušejte implementace porovnat s různým počtem úkolů (Task).

<note tip> Jak přidat úkoly ...
<code java> 
int initTaskCount = 10000;
boolean verbose = false;
</code></note>

===== Domácí úkol =====
[[courses:a0b36pr1:hw:lab12|]]