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 • •