Zadanie skúšky z 11.1.2019

Implementujte 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 jeho vyhodením z BVS. Tento prioritný front môžeme využiť na triedenie bežným spôsobom: najprv sa všetky prvky triedeného poľa postupne presunú do prioritného frontu a potom pomocou metódy remove_min sa postupne všetky vrátia späť do poľa ale už v utriedenom poradí.

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ú jednosmernými spájanými zoznamami: 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;
  • prvky jednosmerných spájaných zoznamov realizujte dátovou štruktúrou Item, v ktorej v atribúte next budete ukladať nasledovný prvok zoznamu;
  • keď sa bude zo stromu odoberať nejaká 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;
  • uvedomte si, že z tohto BVS sa budú odstraňovať len vrcholy s minimálnym kľúčom, teda sú to len také vrcholy, ktoré nemajú ľavého syna.

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

class EmptyError(Exception): pass

class Item:
    def __init__(self, value):
        self.value = value
        self.next = None

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value_list = Item(value)
        self.left = self.right = None

class PriorityQueue:
    def __init__(self):
        self.root = None

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

    def remove_min(self):
        return None, None

    ...

def pq_sort(pole):
    pq = PriorityQueue()
    for key, value in pole:
        pq.add(key, value)
    for i in range(len(pole)):
        pole[i] = pq.remove_min()

kde

  • definície tried EmptyError, Item a Node vo svojom riešení nemeňte – 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);
  • metódy add(key,value), min(), remove_min() a __len__() 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 min() a remove_min() vrátia buď dvojicu (typu tuple) pre kľúč a hodnotu alebo vyvolajú výnimku EmptyError;
  • metóda tree_height() vráti momentálnu výšku celého BVS (výška prázdneho stromu je -1);
  • ani funkciu pq_sort() nemá zmysel modifikovať, lebo spúšťať sa bude táto pôvodná verzia.

Váš program môžete testovať napr. takto:

if __name__ == '__main__':
    pole = [(2,'prvy'), (1,'druhy'), (3,3.14), (2,444), (5,'piaty')]
##    pq_sort(pole)
    pq = PriorityQueue()
    for key, value in pole:
        pq.add(key, value)
    print('pocet:', len(pq))
    print('vyska:', pq.tree_height())
    print('min:', pq.min())
    for i in range(len(pole)):
        pole[i] = pq.remove_min()
        print(pole[i], len(pq), pq.tree_height())
    print(pq.remove_min())

Výpis potom bude:

pocet: 5
vyska: 2
min: (1, 'druhy')
(1, 'druhy') 4 2
(2, 'prvy') 3 2
(2, 444) 2 1
(3, 3.14) 1 0
(5, 'piaty') 0 -1
...
EmptyError

V tomto príklade sa zostrojí BVS, ktorý má len 4 vrcholy, 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. Vo vašom riešení nepoužívajte funkcie sort ani sorted.

Aby ste mohli spúšťať skúškové testy, program uložte do súboru skuska.py.

Riešenie odovzdajte na úlohový server L.I.S.T..

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



© Copyright 2018-2019, Andrej Blaho.
Naposledy aktualizované 14. feb. 2019.
Vytvorené pomocou Sphinx 1.8.4.

Creative Commons License This work is licensed under a Creative Commons Attribution 4.0 International License.