Prioritní fronta, Halda
Metodický koncept k efektivní podpoře klíčových odborných kompetencí s využitím cizího jazyka
ATCZ62 - CLIL jako výuková strategie na vysoké škole
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Prioritní fronta – ADT
•Prioritní fronta uchovává kolekci položek
•Položka je uspořádaná dvojice klíč (priorita) a hodnota
•Základní operace s prioritní frontou
•insertItem(k, o) removeMin()
•Další operace:
•minKey(k, o) minElement()
•size() isEmpty()
•Aplikace:
•Aukce, burzy…

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Prioritní fronta

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Halda (Heap)
Poslední
uzel

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Haldy a prioritní fronty
•Prioritní frontu lze implementovat pomocí haldy
•Ukládáme položku (klíč, hodnota) v každém interním uzlu
•Uchováváme odkaz na pozici posledního prvku
•

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Halda – vložení, odebrání
•Operace insertItem(k, o)
•Nalezení uzlu, kam se bude vkládat
•Uložení klíče k do uzlu z, změna uzlu z na interní uzel
•Obnovení uspořádanosti haldy (kontrola vlastností) – operace upheap()
•Operace removeMin()
•Odpovídá odebrání kořene z hromady (uzel 2)
•Výměna kořene za poslední uzel (2 – 7)
•Změna uzlu w a jeho dětí na list
•Obnovení uspořádanosti haldy – operace downheap()
•
Uzel pro vkládání
w
w

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Obnovení uspořádanosti haldy
•upheap()
•Vložení uzlu může narušit uspořádání
•Algoritmus upheap obnoví uspořádání prohazováním klíče k vzhůru od vloženého uzlu
•Končí ve chvíli, kdy se vložený uzel stane kořenem, nebo když rodičovský klíč je roven nebo menší
než k
•downheap()
•Odebrání kořene může narušit uspořádání
•Algoritmus downheap obnoví uspořádání prohazováním klíče k dolů od kořene
•Končí ve chvíli, kdy se vložený uzel stane listem, nebo když klíč potomka je roven nebo větší než
k
•
•