Skúška 24.1.2020 - double-ended priority queue


Implementuj obojstranný prioritný front pomocou binárneho vyhľadávacieho stromu: vkladanie nového prvku (metóda add) je štandardným vložením do BVS, vyhodenie minimálnej hodnoty (metóda remove_min) je štandardným hľadaním minimálneho prvku a prípadne aj jeho vyhodením z BVS. Keďže prioritný front je obojstranný (double-ended), bude treba implementovať aj metódy pre maximálne hodnoty, t.j. get_max a remove_max (vyhodenie maximálnej hodnoty).

Binárny strom BVS sa pre účely prioritného frontu musí trochu prispôsobiť:

  • keďže sa do frontu môže vložiť viac dvojíc (kľúč, hodnota) s rovnakým kľúčom (možno aj s rovnakou hodnotou), musíme zabezpečiť správne fungovanie BVS;

  • vo vrcholoch BVS (typu _Node) budú všetky kľúče rôzne, ale prislúchajúce hodnoty sa v každom vrchole uchovávajú v pythonovskom zozname (list): na začiatku každého zoznamu sa nachádza hodnota, ktorá bola s daným kľúčom vložená do stromu ako prvá, za tým nasledujú všetky ďalšie hodnoty s daným kľúčom v poradí, ako sa vkladali do stromu;

  • keď sa bude zo stromu odoberať minimálna hodnota, vždy sa zoberie hodnota zo začiatku zoznamu; keď sa takto príslušný zoznam vyprázdni, bude treba odstrániť samotný vrchol BVS;

  • keď sa bude zo stromu odoberať maximálna hodnota, vždy sa zoberie hodnota z konca zoznamu; keď sa takto príslušný zoznam vyprázdni, bude treba odstrániť samotný vrchol BVS (podobne to bude aj pre metódu get_max);

  • uvedom si, že z tohto BVS sa budú odstraňovať len vrcholy s minimálnym, resp. maximálnym kľúčom, teda sú to len také vrcholy, ktoré nemajú ľavého, resp. pravého syna.

Použi tieto deklarácie (z úlohového servera L.I.S.T. si stiahni kompletnú verziu skuska.py):

class EmptyError(Exception): pass

class PriorityQueue:
    class _Node:
        def __init__(self, key, value):
            self.key = key
            self.value_list = [value]
            self.left = self.right = None

    def __init__(self):
        self._root = None

    def add(self, key, value):
        ...

    def get_min(self):
        return None, None

    def remove_min(self):
        return None, None

    def get_max(self):
        return None, None

    def remove_max(self):
        return None, None

    def __len__(self):
        return 0

kde

  • definície tried EmptyError a _Node vo svojom riešení nemeň – testovač aj tak použije presne túto definíciu týchto tried;

  • atribút _root v triede PriorityQueue musí obsahovať koreň BVS, pre prázdny strom musí obsahovať None (testovač to kontroluje)

  • všetky metódy add(key,value), get_min(), … by sa mali správať ako bežné metódy prioritného frontu, t.j. mali by modifikovať BVS (s koreňom v _root), prípadne poskytovať o ňom požadované informácie; metódy get_min(), get_max(), remove_min() a remove_max() vrátia buď dvojicu (typu tuple) pre kľúč a hodnotu alebo vyvolajú výnimku EmptyError

Program môžeš testovať, napríklad takto:

if __name__ == '__main__':
    pq = PriorityQueue()
    for key, value in (2, 'prvy'), (1, 'druhy'), (3, 3.14), (2, 444), (5, 'piaty'):
        pq.add(key, value)
    print('pocet:', len(pq))
    print('min:', pq.get_min())
    print('max:', pq.get_max())
    while len(pq):
        print('remove_min:', pq.remove_min())
        print('remove_max:', pq.remove_max())

Výpis potom bude:

pocet: 5
min: (1, 'druhy')
max: (5, 'piaty')
remove_min: (1, 'druhy')
remove_max: (5, 'piaty')
remove_min: (2, 'prvy')
remove_max: (3, 3.14)
remove_min: (2, 444)
...
EmptyError

V tomto príklade sa zostrojí BVS, ktorý má len 5 vrcholov, pričom vo vrchole s kľúčom 2 sú uložené 2 hodnoty v poradí najprv 'prvy' a potom 444. Vo všetkých ostatných vrcholoch je len po jednej hodnote. V riešení nepoužívaj funkcie sort ani sorted.

Aby si mohol spúšťať skúškové testy, riešenie odovzdaj na úlohový server L.I.S.T.. Testy postupne preverujú vlastnosti tvojich algoritmov, pri prvej chybe sa testovanie preruší a ďalšie časti sa netestujú.

Praktická časť končí o 11:00 a skúška ďalej pokračuje od 12:00 vyhodnotením v kancelárii m162.