A Hromada je úplná binárna stromová dátová štruktúra, ktorá spĺňa vlastnosť haldy: pre každý uzol je hodnota jeho potomkov menšia alebo rovná jeho vlastnej hodnote. Hromady sa zvyčajne používajú na implementáciu prioritných frontov, kde najmenší (alebo najväčší) prvok je vždy v koreni stromu.

Štruktúra údajov haldy

Obsah

• Typy hromady
• Operácie haldy
• Čo je to štruktúra údajov haldy?

  A hromada je binárna stromová dátová štruktúra, ktorá spĺňa vlastnosť haldy: hodnota každého uzla je väčšia alebo rovná hodnote jeho potomkov. Táto vlastnosť zabezpečuje, že koreňový uzol obsahuje maximálne alebo minimálne hodnotu (v závislosti od typu haldy) a hodnoty sa pri pohybe nadol v strome znižujú alebo zvyšujú.

  Typy hromady

  Existujú dva hlavné typy hromady:

  
  
  
  
  • Maximálna halda: Koreňový uzol obsahuje maximálnu hodnotu a pri pohybe nadol v strome sa hodnoty znižujú.
  • Minimálna halda: Koreňový uzol obsahuje minimálnu hodnotu a hodnoty sa zvyšujú, keď sa pohybujete v strome nadol.

  Operácie haldy

  Bežné operácie s haldou sú:

  • Vložiť : Pridá nový prvok do haldy pri zachovaní vlastnosti haldy.
  • Extrahovať Max/Min: Odstráni maximálny alebo minimálny prvok z haldy a vráti ho.
  • Heapify : Konvertuje ľubovoľný binárny strom na hromadu.

  Hromady sa bežne používajú na implementáciu prioritných frontov, kde sa prvky získavajú na základe ich priority (maximálna alebo minimálna hodnota).

• Heapsort je triediaci algoritmus, ktorý používa haldu na triedenie poľa vo vzostupnom alebo zostupnom poradí.
• Hromady sa používajú v grafových algoritmoch ako napr Dijkstrov algoritmus a Primov algoritmus na nájdenie najkratších ciest a minima stromov.

Binárna halda

Aplikácie, výhody a nevýhody haldy

Časová náročnosť výstavby haldy

Porovnanie haldy a stromu

Je pri budovaní haldy jedinečná štruktúra haldy?

Fibonacciho halda

Ľavicová halda

K-ary Halda

Hromadné triedenie

Skontrolujte, či je daný binárny strom halda

Ako skontrolovať, či dané pole predstavuje binárnu haldu?

Iteratívne triedenie haldy

K’th Najväčší prvok v poli

K’th najmenší/najväčší prvok v netriedenom poli | Set 1

Výška úplného binárneho stromu (alebo haldy) s N uzlami

Halda Triediť na zníženie poradia pomocou min haldy

Vytlačte všetky uzly menšie ako hodnota x v Min halde.

Strom turnaja (strom víťaza) a binárna halda

Spojte n lán s minimálnymi nákladmi

Maximálne zreteľné prvky po odstránení k prvkov

K maximálnych súčtových kombinácií z dvoch polí

Medián toku bežiacich celých čísel pomocou STL

Medián v prúde celých čísel (bežné celé čísla)

K’th najväčší prvok v prúde

Najväčší trojitý produkt v prúde

Nájdite k čísel s najväčším počtom výskytov v danom poli

Previesť minimálnu haldu na maximálnu haldu

Pri danej úrovni poradia prechodu binárneho stromu skontrolujte, či je strom mini-hromada

Zlúčiť k triedené polia | Set 1

Zoraďte čísla uložené na rôznych strojoch

Najmenšia odchýlka v sekvencii

Najväčšia odchýlka v sekvencii

Maximálny rozdiel medzi dvoma podmnožinami m prvkov

Konvertovať BST na minimálnu haldu

Zlúčte dve binárne Max haldy

K-té súvislé podpolie s najväčšou sumou

Minimálny súčin k celých čísel v poli kladných celých čísel

Zmeňte usporiadanie znakov v reťazci tak, aby žiadne dva susediace neboli rovnaké

Súčet všetkých prvkov medzi k1’th a k2’th najmenších prvkov

Minimálny súčet dvoch čísel vytvorených z číslic poľa

Rýchle odkazy:

• Cvičné problémy na halde
• Odporúčané:
  • Naučte sa dátovú štruktúru a algoritmy | Príručka DSA