Phenquestions
Ilustrarea structurilor de date Heap
Există două tipuri de grămezi: un max-heap și un min-heap. O structură max-heap este în cazul în care valoarea maximă este rădăcina, iar valorile devin mai mici pe măsură ce arborele este coborât; orice părinte are o valoare egală sau mai mare decât oricare dintre copiii săi apropiați. O structură min-heap este unde valoarea minimă este rădăcina, iar valorile devin mai mari pe măsură ce arborele este coborât; orice părinte are o valoare egală sau mai mică decât oricare dintre copiii săi apropiați. În următoarele diagrame, prima este un maxim-heap și a doua este un min-heap:
Pentru ambele grămezi, observați că pentru o pereche de copii, nu contează dacă cel din stânga este valoarea cea mai mare. Un rând dintr-un nivel din copac nu trebuie neapărat să fie umplut de la minim la maxim, din stânga; de asemenea, nu este neapărat umplut de la maxim la minim, de la stânga.
Reprezentând o grămadă într-o matrice
Pentru ca software-ul să poată utiliza cu ușurință un heap, acesta trebuie să fie reprezentat într-o matrice. Max-heap de mai sus, reprezentat într-o matrice este:
89, 85, 87, 84, 82, 79, 73, 80, 81,,, 65, 69Acest lucru se face începând cu valoarea rădăcină ca prima valoare pentru matrice. Valorile sunt plasate continuu citind arborele de la stânga la dreapta, de sus în jos. Dacă un element este absent, poziția sa în matrice este omisă. Fiecare nod are doi copii. Dacă un nod este la index (poziție) n, primul său copil din matrice este la index 2n + 1, iar următorul său copil este la index 2n + 2. 89 este la index 0; primul său copil, 85 este la index 2 (0) + 1 = 1 în timp ce al doilea copil este la index 2 (0) + 2 = 2. 85 este la indexul 1; primul său copil, 84, este la indexul 2 (1) + 1 = 3 în timp ce al doilea copil al acestuia, 82 este la indexul 2 (1) + 2 = 4. 79 este la indexul 5; primul său copil, 65 este la index 2 (5) + 1 = 11 în timp ce al doilea copil este la index 2 (5) + 2 = 12. Formulele sunt aplicate restului elementelor din matrice.
O astfel de matrice, în care semnificația unui element și relația dintre elemente, este implicată de poziția elementului, se numește o structură de date implicită.
Structura de date implicită pentru min-heap-ul de mai sus este:
65, 68, 70, 73, 71, 83, 84,,, 79, 80,,, 85, 89Max-heap-ul de mai sus este un arbore binar complet, dar nu un arbore binar complet. De aceea unele locații (poziții) sunt goale în matrice. Pentru un arbore binar complet, nicio locație nu va fi goală în matrice.
Acum, dacă grămada ar fi un arbore aproape complet, de exemplu, dacă lipsea valoarea 82, matricea ar fi:
89, 85, 87, 84,, 79, 73, 80, 81,,, 65, 69În această situație, trei locații sunt goale. Cu toate acestea, formulele sunt încă aplicabile.
Operațiuni
O structură de date este un format de date (e.g. un copac), plus relația dintre valori, plus operațiile (funcțiile) efectuate asupra valorilor. Pentru o grămadă, relația care trece prin întreaga grămadă este că părintele trebuie să aibă o valoare egală sau mai mare decât copiii, pentru o grămadă maximă; iar părintele trebuie să aibă o valoare egală sau mai mică decât copiii, pentru o min-grămadă. Această relație se numește proprietatea heap. Operațiunile unei grămezi sunt grupate sub rubricile Creație, Bază, Internă și Inspecție. Urmează un rezumat al operațiunilor heap-ului:
Sumar operațiuni Heap
Există anumite operațiuni software care sunt obișnuite cu grămezi, după cum urmează:
Crearea unui Heap
create_heap: Crearea unei grămezi înseamnă formarea unui obiect care reprezintă grămada. În limbajul C, puteți crea o grămadă cu tipul de obiect struct. Unul dintre membrii structului va fi matricea heap. Restul membrilor vor fi funcții (operații) pentru heap. Create_heap înseamnă crearea unui heap gol.
Heapify: matricea heap este o matrice parțial sortată (ordonată). Heapify înseamnă, furnizați o matrice heap dintr-o matrice nesortată - consultați detaliile de mai jos.
Îmbinare: Aceasta înseamnă, formează o grămadă de uniune din două grămezi diferite - vezi detaliile de mai jos. Cele două grămezi ar trebui să fie max-heap sau ambele min-heap. Noua grămadă este în conformitate cu proprietatea grămezii, în timp ce grămezile originale sunt păstrate (nu șterse).
Combinare: Aceasta înseamnă, uniți două grămezi de același tip pentru a forma una nouă, păstrând duplicate - consultați detaliile de mai jos. Noua grămadă este în conformitate cu proprietatea grămezii, în timp ce grămezile originale sunt distruse (șterse). Principala diferență între fuzionare și fuzionare este că, pentru fuzionare, un arbore se potrivește ca subarborescență la rădăcina celuilalt arbore, permițând valori duplicate în noul arbore, în timp ce pentru fuziune se formează un nou arbore heap, eliminând duplicatele. Nu este nevoie să întrețineți cele două grămezi originale prin topire.
Operațiuni de bază Heap
find_max (find_min): Găsiți valoarea maximă în tabloul max-heap și returnați o copie sau localizați valoarea minimă în tabloul min-heap și returnați o copie.
Inserați: adăugați un element nou la matricea heap și rearanjați matricea astfel încât proprietatea heap a diagramei să fie menținută.
extract_max (extract_min): Găsiți valoarea maximă în matricea max-heap, eliminați-o și returnați-o; sau localizați valoarea minimă în matricea min-heap, scoateți-o și returnați-o.
delete_max (delete_min): Găsiți nodul rădăcină al unui max-heap, care este primul element al matricei max-heap, eliminați-l fără a-l returna neapărat; sau localizați nodul rădăcină al unui min-heap, care este primul element al matricei min-heap, eliminați-l fără a-l returna neapărat;
Înlocuiți: localizați nodul rădăcină al oricărui heap, eliminați-l și înlocuiți-l cu unul nou. Nu contează dacă vechea rădăcină este returnată.
Operații interne de heap
mărire_cheie (micșorare_cheie): Măriți valoarea oricărui nod pentru un heap maxim și rearanjați astfel încât proprietatea heap să fie menținută sau micșorați valoarea oricărui nod pentru un min-heap și rearanjați astfel încât proprietatea heap să fie menținută.
Șterge: șterge orice nod, apoi rearanjează, astfel încât proprietatea heap să fie menținută pentru max-heap sau min-heap.
shift_up: mutați un nod în sus într-un max-heap sau min-heap atât timp cât este necesar, rearanjându-vă pentru a menține proprietatea heap.
shift_down: mutați un nod în jos într-un heap maxim sau min-heap atât timp cât este necesar, rearanjându-vă pentru a menține proprietatea heap.
Inspecția unei grămezi
Mărimea: Aceasta returnează numărul de taste (valori) dintr-o grămadă; nu include locațiile goale ale matricei de heap. O grămadă poate fi reprezentată prin cod, ca în diagramă, sau cu o matrice.
este gol: Acest lucru returnează Boolean adevărat dacă nu există nod într-o grămadă, sau Boolean fals dacă grămada are cel puțin un nod.
Cernere într-o grămadă
Există sift-up și sift down:
Sift-Up: Aceasta înseamnă să schimbați un nod cu părintele său. Dacă proprietatea heap nu este satisfăcută, schimbați părintele cu propriul său părinte. Continuați în acest fel în cale până când proprietatea heap este satisfăcută. Procedura ar putea ajunge la rădăcină.
Sift-Down: Acest lucru înseamnă să schimbați un nod de mare valoare cu cel mai mic dintre cei doi copii ai săi (sau un copil pentru o grămadă aproape completă). Dacă proprietatea heap nu este satisfăcută, schimbați nodul inferior cu nodul mai mic al propriilor doi copii. Continuați în acest fel în cale până când proprietatea heap este satisfăcută. Procedura ar putea ajunge la o frunză.
Heapifying
Heapify înseamnă sortarea unei matrice nesortate pentru a avea proprietatea heap satisfăcută pentru max-heap sau min-heap. Aceasta înseamnă că ar putea exista unele locații goale în noua matrice. Algoritmul de bază pentru a heapify un max-heap sau min-heap este după cum urmează:
- dacă nodul rădăcină este mai extrem decât oricare dintre nodul copilului său, atunci schimbați rădăcina cu nodul copil mai puțin extrem.
- Repetați acest pas cu nodurile copiilor dintr-o schemă de precomandă de traversare a copacilor.
Arborele final este un copac heap care satisface proprietatea heap. O grămadă poate fi reprezentată ca o diagramă de copac sau într-o matrice. Heapul rezultat este un copac parțial sortat, i.e. o matrice parțial sortată.
Detalii despre operațiunea Heap
Această secțiune a articolului oferă detalii despre operațiunile de heap.
Crearea unui Heap Details
create_heap
Vezi deasupra!
heapify
Vezi deasupra
combina
Dacă matricea heap,
89, 85, 87, 84, 82, 79, 73, 80, 81,,, 65, 69și
89, 85, 84, 73, 79, 80, 83, 65, 68, 70, 71sunt îmbinate, rezultatul fără duplicate poate fi,
89, 85, 87, 84, 82, 83, 81, 80, 79,, 73, 68, 65, 69, 70, 71După niște cerne. Observați că în prima matrice, 82 nu are copii. În matricea rezultată, se află la indexul 4; iar locațiile sale la indexul 2 (4) + 1 = 9 și 2 (4) + 2 = 10 sunt vacante. Aceasta înseamnă că, de asemenea, nu are copii în noua diagramă a arborelui. Cele două grămezi originale nu trebuie șterse, deoarece informațiile lor nu se află într-adevăr în noua grămadă (matrice nouă). Algoritmul de bază pentru a îmbina grămezi de același tip este după cum urmează:
- Alăturați o matrice la partea de jos a celeilalte matrice.
- Heapify elimină duplicatele, asigurându-se că nodurile care nu au avut copii în grămezile originale, încă nu au copii în noua grămadă.
meld
Algoritmul pentru combinarea a două grămezi de același tip (fie două max-, fie două min-) este după cum urmează:
- Comparați cele două noduri rădăcină.
- Faceți rădăcina mai puțin extremă și restul arborelui său (subarborele), al doilea copil al rădăcinii extreme.
- Cerneți copilul rătăcit al rădăcinii acum subarborelui extrem, în jos în subarborele extrem.
Grămada rezultată este încă în conformitate cu proprietatea grămezii, în timp ce grămezile originale sunt distruse (șterse). Grămezile originale pot fi distruse, deoarece toate informațiile pe care le dețin sunt încă în noua grămadă.
Operațiuni de bază Heap
find_max (find_min)
Aceasta înseamnă să localizați valoarea maximă în matricea max-heap și să returnați o copie sau să localizați valoarea minimă în matricea min-heap și să returnați o copie. O matrice de heap, prin definiție, satisface deja proprietatea heap. Deci, trebuie doar să returnați o copie a primului element al matricei.
introduce
Aceasta înseamnă să adăugați un element nou la matricea heap și să rearanjați tabloul astfel încât proprietatea heap a diagramei să fie menținută (satisfăcută). Algoritmul pentru a face acest lucru pentru ambele tipuri de grămezi este după cum urmează:
- Să presupunem un copac binar complet. Aceasta înseamnă că tabloul trebuie completat la sfârșit cu locații goale, dacă este necesar. Numărul total de noduri ale unui heap complet este 1, sau 3 sau 7 sau 15 sau 31, etc.; continuați să dublați și să adăugați 1.
- Puneți nodul în cea mai potrivită locație goală după mărime, spre sfârșitul heap-ului (spre sfârșitul matricei heap). Dacă nu există o locație goală, atunci începeți un rând nou din partea stângă jos.
- Cercetați în sus, dacă este necesar, până când proprietatea heap este satisfăcută.
extract_max (extract_min)
Localizați valoarea maximă în matricea max-heap, eliminați-o și returnați-o; sau localizați valoarea minimă în matricea min-heap, scoateți-o și returnați-o. Algoritmul pentru extract_max (extract_min) este după cum urmează:
- Eliminați nodul rădăcină.
- Luați (eliminați) nodul din dreapta jos (ultimul nod din matrice) și plasați-l la rădăcină.
- Cerneți în jos, după caz, până când proprietatea heap este satisfăcută.
delete_max (delete_min)
Localizați nodul rădăcină al unui max-heap, care este primul element al matricei max-heap, eliminați-l fără a-l returna neapărat; sau localizați nodul rădăcină al unui min-heap, care este primul element al matricei min-heap, eliminați-l fără a-l returna neapărat. Algoritmul pentru ștergerea nodului rădăcină este următorul:
- Eliminați nodul rădăcină.
- Luați (eliminați) nodul din dreapta jos (ultimul nod din matrice) și plasați-l la rădăcină.
- Cerneți în jos, după caz, până când proprietatea heap este satisfăcută.
a inlocui
Localizați nodul rădăcină al oricărui heap, eliminați-l și înlocuiți-l cu cel nou. Nu contează dacă vechea rădăcină este returnată. Cerneți în jos, dacă este cazul, până când proprietatea heap este satisfăcută.
Operații interne de heap
creștere_cheie (reducere_cheie)
Măriți valoarea oricărui nod pentru un heap maxim și rearanjați astfel încât proprietatea heap să fie menținută sau micșorați valoarea oricărui nod pentru un min-heap și rearanjați astfel încât proprietatea heap să fie menținută. Treceți în sus sau în jos, după caz, până când proprietatea heap este satisfăcută.
șterge
Eliminați nodul de interes, apoi rearanjați, astfel încât proprietatea heap să fie menținută pentru max-heap sau min-heap. Algoritmul pentru ștergerea unui nod este după cum urmează:
- Eliminați nodul de interes.
- Luați (eliminați) nodul din dreapta jos (ultimul nod din matrice) și plasați la indexul nodului eliminat. Dacă nodul șters este pe ultimul rând, este posibil să nu fie necesar.
- Treceți în sus sau în jos, după caz, până când proprietatea heap este satisfăcută.
shift_up
Mutați un nod în sus într-un heap maxim sau min-heap atât timp cât este necesar, rearanjându-vă pentru a menține proprietatea heap - cernere în sus.
shift_down
Mutați un nod în jos într-un heap maxim sau min-heap atât timp cât este necesar, rearanjându-vă pentru a menține proprietatea heap - cernere în jos.
Inspecția unei grămezi
mărimea
Vezi deasupra!
este gol
Vezi deasupra!
Alte clase de grămezi
Heap-ul descris în acest articol poate fi considerat ca heap-ul principal (general). Există și alte clase de grămezi. Cu toate acestea, cele două pe care ar trebui să le cunoașteți dincolo de acestea sunt Heapul Binar și D-Ary Heap.
Heap binar
Heapul binar este similar cu acest heap principal, dar cu mai multe constrângeri. În special, heap-ul binar trebuie să fie un arbore complet. Nu confundați între un copac complet și un copac plin.
d-ary Heap
O grămadă binară este o grămadă de 2 arii. O grămadă în care fiecare nod are 3 copii este o grămadă de 3 arii. O grămadă în care fiecare nod are 4 copii este o grămadă de 4 ari și așa mai departe. O grămadă d-ari are alte constrângeri.
Concluzie
O grămadă este un arbore binar complet sau aproape complet, care satisface proprietatea grămezii. Proprietatea heap are 2 alternative: pentru un max-heap, un părinte trebuie să aibă o valoare egală sau mai mare decât copiii imediați; pentru un min-heap, un părinte trebuie să aibă o valoare egală sau mai mică decât copiii imediați. O grămadă poate fi reprezentată ca un copac sau într-o matrice. Când este reprezentat într-o matrice, nodul rădăcină este primul nod al matricei; și dacă un nod este la indexul n, primul său copil din matrice este la indexul 2n + 1 și următorul său copil este la indexul 2n + 2. O grămadă are anumite operații care sunt efectuate pe matrice.
Chrys
