Ce este o stivă (în contextul structurilor de date)?

Un heap este un arbore specializat utilizat ca structură de date. Proprietatea principală a heap-ului este ordonarea parțială: pentru orice vârf, condiția este ca valoarea vârfului părinte să fie mai mare sau egală cu valoarea oricărui dintre copiii săi (max-heap) sau mai mică sau egală (min-heap).

Caracteristici cheie:

• Arbore binar: De obicei implementat ca un arbore binar, unde fiecare nod are cel mult doi descendenți.
• Arbore binar complet: Pe toate nivelurile, cu excepția posibil ultimei, arborele este complet umplut. Nodurile de pe ultimul nivel sunt umplute de la stânga la dreapta. Acest lucru permite stocarea eficientă a heap-ului sub formă de array.
• Proprietatea heap-ului:
  • Max-heap: Valoarea fiecărui nod este mai mare sau egală cu valorile descendenților săi. Elementul maxim se află întotdeauna în rădăcină.
  • Min-heap: Valoarea fiecărui nod este mai mică sau egală cu valorile descendenților săi. Elementul minim se află întotdeauna în rădăcină.

Operații principale cu heap-ul:

• Inserarea unui element: Adăugarea unui nou element și menținerea proprietății heap-ului.
• Eliminarea unui element: Eliminarea elementului rădăcină (maxim sau minim, în funcție de tipul de heap) și menținerea proprietății heap-ului.
• Construirea heap-ului: Construirea unui heap dintr-un array de elemente.

Aplicații ale heap-ului:

• Sortare: Algoritmul de sortare prin heap (Heapsort).
• Cozi de prioritate: Implementare eficientă a cozilor în care elementele sunt procesate în ordinea priorității.
• Algoritmi de căutare: De exemplu, căutarea elementului k-ésimo după valoare.
• Algoritmi pe grafuri: De exemplu, algoritmul lui Dijkstra.

Reprezentarea heap-ului în array:

Deoarece heap-ul este un arbore binar complet, poate fi stocat eficient în array fără utilizarea pointerilor.

• Dacă un nod se află la indexul i, copilul său stâng se află la indexul 2*i + 1.
• Copilul său drept se află la indexul 2*i + 2.
• Părintele său se află la indexul (i - 1) / 2.

# Exemplu de reprezentare a unui min-heap sub formă de array
heap_array = [10, 15, 20, 17, 25, 30]

# Rădăcină: heap_array[0] = 10
# Copilul stâng al rădăcinii: heap_array[2*0 + 1] = heap_array[1] = 15
# Copilul drept al rădăcinii: heap_array[2*0 + 2] = heap_array[2] = 20
# Părintele elementului de la indexul 3 (17): heap_array[(3-1)//2] = heap_array[1] = 15