A Morman este o structură de date binară completă care satisface proprietatea heap: pentru fiecare nod, valoarea copiilor săi este mai mică sau egală cu propria sa valoare. Heap-urile sunt de obicei folosite pentru a implementa cozi de prioritate, unde cel mai mic (sau cel mai mare) element este întotdeauna la rădăcina arborelui.

Structura de date heap

Cuprins

• Tipuri de grămezi
• Operațiuni Heap
• Ce este Heap Data Structure?

  A morman este o structură de date bazată pe arbore binar care satisface proprietatea heap: valoarea fiecărui nod este mai mare sau egală cu valoarea copiilor săi. Această proprietate asigură că nodul rădăcină conține maxim sau minim valoare (în funcție de tipul de grămadă), iar valorile scad sau cresc pe măsură ce vă deplasați în jos în copac.

  Tipuri de grămezi

  Există două tipuri principale de grămezi:

  
  
  
  
  • Heap maxim: Nodul rădăcină conține valoarea maximă, iar valorile scad pe măsură ce vă deplasați în jos în arbore.
  • Min Heap: Nodul rădăcină conține valoarea minimă, iar valorile cresc pe măsură ce vă deplasați în jos în arbore.

  Operațiuni Heap

  Operațiunile heap comune sunt:

  • Introduce : adaugă un nou element la heap, menținând în același timp proprietatea heap.
  • Extrage Max/Min: Îndepărtează elementul maxim sau minim din heap și îl returnează.
  • Heapify : Convertește un arbore binar arbitrar într-un heap.

  Heap-urile sunt utilizate în mod obișnuit pentru a implementa cozi de prioritate, unde elementele sunt preluate în funcție de prioritatea lor (valoarea maximă sau minimă).

• Heapsort este un algoritm de sortare care utilizează un heap pentru a sorta o matrice în ordine crescătoare sau descrescătoare.
• Mulțile sunt folosite în algoritmi grafici precum algoritmul lui Dijkstra și algoritmul lui Prim pentru găsirea celor mai scurte căi și a arborilor de întindere minimă.

Heap binar

Aplicații, avantaje și dezavantaje ale Heap

Timp Complexitatea construirii unui morman

Comparație între Heap și Tree

Când construiți un Heap, este structura Heap unică?

Heap Fibonacci

Heap de stânga

K-ary Heap

Sortare grămadă

Verificați dacă un arbore binar dat este Heap

Cum se verifică dacă o matrice dată reprezintă un heap binar?

Sortare iterativă în grămada

Cel mai mare element al K-a dintr-o matrice

Cel mai mic/cel mai mare element K’ din matricea nesortată | Setul 1

Înălțimea unui arbore binar complet (sau Heap) cu N noduri

Heap Sort pentru ordine descrescătoare utilizând min heap

Tipăriți toate nodurile mai mici decât o valoare x într-un Heap min.

Arborele turneului (Arborele câștigătorilor) și Munții binar

Conectați n frânghii cu costuri minime

Maximum elemente distincte după eliminarea k elemente

K combinații de sumă maximă din două tablouri

Mediana fluxului de numere întregi care rulează folosind STL

Mediana într-un flux de numere întregi (întregi care rulează)

K-ul cel mai mare element dintr-un flux

Cel mai mare produs triplet dintr-un flux

Găsiți k numere cu cele mai multe apariții în matricea dată

Convertiți Heap min în Heap maxim

Având în vedere parcurgerea în ordinea nivelului a unui Arbore Binar, verificați dacă Arborele este un Min-Heap

Merge k tablouri sortate | Setul 1

Sortați numerele stocate pe diferite mașini

Cea mai mică dereglare a secvenței

Cea mai mare tulburare a unei secvențe

Diferența maximă între două submulțimi de m elemente

Convertiți BST în Heap min

Îmbină două blocuri binare Max

K-a cea mai mare sumă Subbarray contiguă

Produsul minim de k numere întregi într-o matrice de numere întregi pozitive

Rearanjați caracterele într-un șir astfel încât să nu fie două adiacente la fel

Suma tuturor elementelor dintre k1-a și k2-a cel mai mic element

Suma minimă a două numere formată din cifrele unui tablou

Link-uri rapide:

• Practicați problemele pe Heap
• Recomandat:
  • Aflați structura datelor și algoritmi | Tutorial DSA