Deci, trecem treptat de la metode mai mult sau mai puțin simple la cele complexe, dar eficiente. Sortarea cu piramide este prima dintre metodele considerate, a căror performanță este estimată ca O (n log n).
Ca preludiu la metoda de bază, luați în considerare o alegere inversată. În timpul trecerii, în loc să inserăm cel mai mic element în capătul din stânga al matricei, vom selecta cel mai mare element și vom construi secvența terminată la capătul drept.
Exemplu de acțiuni pentru matricea a [0]. a [7]:
Marginea stângă a părții deja sortate (partea dreaptă) a matricei este marcată cu o linie verticală.
Luați în considerare evaluarea numărului de operațiuni în detaliu.
În total, se fac n trepte, fiecare dintre care constă în selectarea celui mai mare element din secvența a [0] .. a [i] și schimbul ulterior. Alegerea este o căutare secvențială a elementelor secvenței, deci timpul necesar pentru aceasta: O (n). Astfel, n etapele în O (n) fiecare este O (n2).
Facem o îmbunătățire: construim o structură de date care ne permite să alegem elementul maxim al secvenței nu pentru O (n), ci pentru timpul O (logn). Atunci viteza generală de sortare va fi n * O (logn) = O (n log n).
Această structură ar trebui să vă permită, de asemenea, să introduceți rapid elemente noi (pentru ao construi rapid din matricea sursă) și să eliminați elementul maxim (acesta va fi plasat în partea deja ordonată a matricei - capătul său drept).
Deci, numim o piramidă (Heap) un copac binar de înălțime k, în care
- toate nodurile au o adâncime k sau k-1 - un copac echilibrat.
- nivelul k-1 este complet umplut și nivelul k este umplut de la stânga la dreapta, adică forma piramidei are aproximativ următoarea formă:
- "proprietatea piramidei" este îndeplinită: fiecare element este mai mic sau egal cu cel al părintelui.
Cum se păstrează piramida? Cel mai puțin deranjant este să o puneți într-o matrice.
Corespondența dintre structura geometrică a unei piramide ca arbore și o matrice este stabilită în conformitate cu următoarea schemă:
- a [0] stochează rădăcina copacului
- fiii stângi și drepți ai elementului a [i] sunt stocați, respectiv, într-un [2i + 1] și un [2i + 2]
Astfel, pentru o matrice care conține o piramidă, se află următoarea proprietate caracteristică: a [i]> = a [2i + 1] și a [i]> = a [2i + 2].
Avantajele stocării piramidei sunt evidente:
- fără variabile suplimentare, trebuie doar să înțelegeți schema.
- nodurile sunt stocate din partea superioară și în jos, nivel de nivel.
- nodurile de același nivel sunt stocate în matrice de la stânga la dreapta.
Vom scrie sub forma unei matrice piramida arătată mai sus. De la stânga la dreapta, de sus în jos: 94 67 18 44 55 12 06 42. În figură, locul elementului piramidal în matrice este indicat de figura din partea dreaptă a acestuia.
Pentru a restaura o piramidă dintr-o matrice ca obiect geometric este ușor - amintiți-vă doar schema de stocare și trageți, pornind de la rădăcină.
Faza 1 sortare: construirea unei piramide
Puteți începe să construiți o piramidă cu un [k]. a [n], k = [dimensiunea / 2]. Această parte a matricei satisface proprietatea piramidei, deoarece nu există indici i, j: i = 2i + 1 (sau j = 2i + 2). Pur și simplu pentru că astfel, i, j sunt în afara limitei matricei.
Trebuie notat că este greșit să spunem că o [k] .. a [n] este o piramidă ca o matrice independentă. Aceasta, în general, nu este adevărată: elementele sale pot fi arbitrare. Proprietatea piramidei este păstrată numai în interiorul matricei principale inițiale [0]. a [n].
Apoi, extindem o parte a matricei care are o proprietate utilă, adăugând un element pe fiecare pas. Următorul element din fiecare etapă a adăugării este cel care se află în fața părții finisate.
Pentru a păstra piramida când adăugăm un element, vom folosi următoarea procedură pentru extinderea piramidei a [i + 1] .. a [n] la elementul a [i] spre stânga:
- Ne uităm la fiii din stânga și din dreapta - în matrice sunt un [2i + 1] și un [2i + 2] și alege cel mai mare dintre ei.
- Dacă acest element este mai mare decât [i] - schimbați-l cu [i] în loc și mergeți la pasul 2, referindu-vă la noua poziție a [i] în matrice. În caz contrar, la sfârșitul procedurii.
Noul element este "cernut" prin piramida.
Luând în considerare faptul că înălțimea piramidei h <= log n, downheap требует O(log n) времени. Полный код процедуры построения пирамиды будет иметь вид:
Mai jos este o ilustrare a procesului pentru o piramidă de 8 elemente:
În interpretarea geometrică, cheile din segmentul inițial a [size / 2]. a [n] este frunzele din arborele binar, după cum se arată mai jos. Unul câte unul, celelalte elemente se mișcă în locurile lor și așa - până când se construiește întreaga piramidă.
Cifrele de mai jos arată procesul de construcție. Partea nepregătită a piramidei (începutul matricei) este pictată alb, sfârșitul matricei care satisface proprietatea piramidei - în cea întunecată.
Faza 2: sortarea în sine
Deci, problema construirii unei piramide dintr-o matrice a fost rezolvată cu succes. După cum se poate observa din proprietățile piramidei, rădăcina este întotdeauna elementul maxim. Aceasta implică algoritmul de fază 2:
- Luăm elementul superior al piramidei [0]. a [n] (primul în matrice) și se schimbă cu ultimele locuri. Acum "uităm" acest element și apoi luăm în considerare matricea [0]. a [n-1]. Pentru ao transforma într-o piramidă, este suficient să trimet doar primul element nou.
- Repetați pasul 1 până când partea prelucrată a matricei este redusă la un element.
Evident, elementul maxim din piramida curentă ajunge de fiecare dată la sfârșitul matricei, astfel încât o secvență ordonată apare treptat în partea dreaptă.
Codul procedurii externe:
Care este viteza algoritmului rezultat?
Construcția piramidei ia operațiuni O (n log n), cu o estimare mai precisă, chiar dând O (n), datorită faptului că timpul de execuție real al downheap-ului depinde de înălțimea părții deja create a piramidei.
Faza a doua ia O (n log n) timp: O (n) de ori maxim este luată și ultimul element ultima este cernut. Plus este stabilitatea metodei: numărul mediu de transferuri (n log n) / 2, iar abaterile de la această valoare sunt relativ mici.
Sortarea Pyramid nu utilizează memorie suplimentară.
Metoda nu este stabilă: în cursul muncii, matricea este "șocată" astfel încât ordinea inițială a elementelor se poate schimba aleatoriu.
Comportamentul este nefiresc: ordonarea parțială a matricei nu este luată în considerare.
Articole similare
Trimiteți-le prietenilor: