Cuprins:
Definiție - Ce înseamnă Heap?
Un morman, în contextul structurii de date, este o structură de date bazată pe arbori care satisface proprietatea heap, unde fiecărui element i se atribuie o valoare cheie sau o pondere. Tasta cu valoare mai mică are întotdeauna un nod părinte cu o cheie cu valoare mai mare. Aceasta se numește o structură max-heap, iar printre toate nodurile, nodul rădăcină are cea mai înaltă cheie.
Uneori, o structură bazată pe arbori are o regulă de structură inversată, în care un element cu o cheie cu valoare mai mare are întotdeauna o cheie de valoare mai mică ca nod parent. Aceasta se numește o structură min-heap, iar printre toate nodurile, nodul rădăcină are cea mai mică cheie.
Techopedia explică Heap
Nu există restricții practice în ceea ce privește numărul de copii pe care fiecare nod le poate avea într-o grămadă, chiar dacă de obicei fiecare nod are două. Mormanul este considerat cea mai eficientă implementare a unui tip de date abstracte, cunoscută sub numele de coadă de prioritate. Implementarea haldei este esențială în diferiți algoritmi de grafic (incluzând algoritmul lui Dijkstra), precum și în algoritmul de sortare a mormântului.
Heaps-urile au mai multe variante care acționează ca implementări de coadă cu prioritate de tip abstract de date. Multe aplicații, cum ar fi algoritmii grafic, necesită implementarea cozilor prioritare.
Un tablou este cea mai comună formă de implementare a mormanului, unde nu este nevoie de indicatori pentru a face legătura între elementele sale.
Mormanele efectuează mai multe operații, inclusiv:
- Find-max: Căutări pentru cel mai înalt nod cheie dintr-un grup de noduri
- Find-min: Căutări pentru cel mai mic nod cheie dintr-un grup de noduri
- Delete-max: Șterge cel mai înalt nod cheie dintr-un grup de noduri
- Delete-min: Șterge cel mai mic nod cheie dintr-un grup de noduri
Mormanele includ, de asemenea, funcții care efectuează fuziunea, introducerea și modificările cheilor.
Această definiție a fost scrisă în contextul structurii de date
