Lab12 - Binární halda

Vaším úkolem je implementovat prioritní frontu binární haldou (BinaryHeap).

package cz.cvut.fel.pr1;
 
import cz.cvut.fel.pr1.provided.BinaryHeap;
import cz.cvut.fel.pr1.provided.Comparator;
import cz.cvut.fel.pr1.provided.PriorityQueue;
import cz.cvut.fel.pr1.provided.Task;
 
public class HeapQueue implements PriorityQueue, BinaryHeap{
 
//implementace
 
}

Po vytvoření třídy HeapQueue je nezbytné implementovat několik metod. Tyto metody jsou předepsány v rozhraní PriorityQueue a BinaryHeap. PriorityQueue předepisuje, že musíte implementovat metody offer() pro přidávání prvků a metody peek() a poll(), které budou vracet prvek s nejvyšší prioritou. Abychom mohli rozhodnout mezi dvěma prvky, který z nich má vyšší prioritu, potřebujeme také tzv. Comparator. Comparator pro naší HeapQueue se bude nastavovat metodou setComparator(). Comparator, který bude používán k porovnávání prvků v haldě, bude získatelný metodou getComparator(). BinaryHeap interface (rozhraní) pro naší HeapQueue navíc předepisuje další dvě metody a to getLeftChild() a getRightChild(), které musíme implementovat tak, že vrátí levého resp. pravého potomka pro Task předaný v argumentu.

V metodách getLeftChild(Task task) a getRightChild(Task task) neřeště efektivitu, když dostanete argument typu Task, tak nevíte kde ho ve své implementaci haldy máte uložený, v této situaci si task ve vaší struktuře jednoduše najděte a pak vraťte jeho příslušného potomka. Při vyhledávání můžete využít i porovnání pomocí “==”, což vám vrátí true, pokud jde o stejnou instanci třidy Task.

V předchozím textu jsme si představili, jak bude HeapQueue vypadat navenek, neboli jaké bude muset mít metody. Nyní si pojďme říci, jaké bude muset HeapQueue mít vlastnosti. Začneme vlastnostmi prioritní fronty. Ty jsou stejné jako u běžné FIFO fronty jen s tím rozdílem, že prvky z fronty vyndaváme v pořadí daném prioritou nikoli pořadím na vstupu (FIFO). Co je pro nás nové, je struktura zvaná binární halda.

Binární halda (EN wikipedia / CS wikipedia je úplný binární strom (binární strom na wikipedii), ve kterém platí tzv. “heap property”, že každý potomek má nižší nebo stejnou hodnotu než rodič sám (v případě max-haldy). V případě kdy není poslední hladina haldy zaplněna, jsou uzly ukládány do haldy zleva.

“Heap property” je rekurzivní - všechny podstromy haldy jsou také haldy. Díky tomu máme zajištěno, že se halda chová jako prioritní fronta.

Tedy platí, že kořen stromu má nejvyšší hodnotu, tedy na výstupu (v našem případě na volání poll() a peek()) je prvek s nejvyšší prioritou.

Máte předepsáno, jak má HeapQueue vypadat navenek (neboli jaké má mít minimálně metody), pak máte určeno jaké vlastnosti má HeapQueue mít (např. vždy vrací prvek s nejvyšší prioritou). Nepředepisujeme Vám, jak má HeapQueue vypadat uvnitř. Ovšem nabízí se použít nějakou datovou strukturu s kterou jste se již setkali. Využít můžete spojovou strukturu jako v minulém úkolu, druhou možností je ukládat si Tasky do pole. V obou případech ale musíte implementovat předepsané metody, aby splňovaly předepsané vlastnosti.

Jelikož se po odebraní nebo přidání vrcholu binární halda může dostat do nekonzistentního stavu, je potřeba haldu opravit při každé takové operaci. Platnost heap property bude průběžně testována.

Odevzdávejte zazipovaný soubor HeapQueue.java

Zkuste si svou implementaci binární haldou porovnat s implementacemi ze cvičení. Měli byste se dostat na řádově lepší časy.