Algoritmul de sortare heap (cu cod în Python și C++)

Ce este algoritmul Heap Sort?

Heap Sort este unul dintre algoritmii de sortare populari și mai rapidi. Este construit pe structura completă a datelor arborelui binar. Vom căuta elementul maxim și îl vom pune în partea de sus pentru grămada maximă. Îl vom pune pe nodul părinte al arborelui binar.

Să presupunem că este dat o matrice, date = [10,5, 7, 9, 4, 11, 45, 17, 60].

În tablou, dacă indicele i-al (i=0,1,2,3 …) este un nod părinte, atunci (2i+1) și (2i+2) vor fi copiii din stânga și din dreapta. Crearea unui arbore binar complet cu această matrice va arăta astfel:

Vom face procesul de heapify de la începutul până la sfârșitul matricei. Inițial, dacă convertim tabloul într-un arbore, acesta va arăta ca cel de mai sus. Putem vedea că nu menține nicio proprietate heap (min-heap sau max heap). Vom obține matricea sortată făcând procesul heapify pentru toate nodurile.

Aplicarea Heap Sort

Iată câteva modalități de utilizare a algoritmului de sortare heap:

Construcția „Cozilor prioritare” necesită sortare în grămada. Deoarece heapsort menține elementul sortat după fiecare inserare.
Heap Data Structure este eficientă în găsirea k^th cel mai mare element dintr-o matrice dată.
Linux Kernel folosește sortarea heap ca implicită algoritm de sortare deoarece are O (1) complexitate spațială.

Creați sortare heap cu exemplu

Aici, vom construi un heap maxim din următorul arbore binar complet.

Nodurile frunzelor sunt 17, 60, 4, 11 și 45. Nu au niciun nod copil. De aceea sunt noduri de frunze. Deci, vom începe metoda heapify de la nodul lor părinte. Iată pașii:

Pas 1) Selectați sub-arborele din stânga. Dacă nodurile copil sunt mai mari, schimbați nodul părinte cu nodul copil.

Aici nodul părinte este 9. Iar nodurile secundare sunt 17 și 60. Deoarece 60 este cel mai mare, 60 și 9 vor fi schimbate pentru a menține heap max.

Pas 2) Acum, subarborele din stânga este îngrămădit. Următorul nod părinte este 7. Acest părinte are două noduri copil, iar cel mai mare este 45. Deci, 45 și 7 vor fi schimbate.

Pas 3) Nodurile 60 și 4 au nodul părinte 5. Deoarece „5” este mai mic decât nodul copil 60, acesta va fi schimbat.

Pas 4) Acum, nodul 5 are nodul copil 17,9. Aceasta nu menține proprietatea maxim heap. Deci, 5 va fi înlocuit cu 17.

Pas 5) Nodul 10 va fi schimbat cu 60, apoi schimbat cu 17. Procesul va arăta ca următorul.

Pas 6) Până la pasul 5, am creat heap-ul maxim. Fiecare nod părinte este mai mare decât nodurile sale secundare. Nodul rădăcină are valoarea maximă (60).

Notă: Pentru a crea matricea sortată, trebuie să înlocuim nodul cu valoarea maximă cu succesorul său.

Acest proces se numește „extract max”. Deoarece 60 este nodul maxim, îi vom fixa poziția la indexul 0 și vom crea heap-ul fără nodul 60.

Pas 7) Pe măsură ce 60 este eliminat, următoarea valoare maximă este 45. Vom face din nou procesul „Extract Max” din nodul 45.

De data aceasta vom obține 45 și vom înlocui nodul rădăcină cu succesorul său 17.

Trebuie să facem "Extras Max” până când toate elementele sunt sortate.

După ce facem acești pași până când extragem toate valorile maxime, vom obține următoarea matrice.

Ce este Binary Heap?

Un morman binar este un fel de complet arbore binar structură de date. În acest tip de structură arborescentă, nodul părinte este fie mai mare, fie mai mic decât nodurile secundare. Dacă nodul părinte este mai mic, atunci heap-ul se numește „Min Heap” și dacă nodul părinte este mai mare, heap-ul se numește „Max Heap”.

Iată exemple de heap min și heap maxim.

În figura de mai sus, dacă observați „Min Heap”, nodul părinte este întotdeauna mai mic decât nodurile sale secundare. În capul copacului, putem găsi cea mai mică valoare 10.

În mod similar, pentru „Max Heap”, nodul părinte este întotdeauna mai mare decât nodurile secundare. Elementul maxim este prezent la nodul principal pentru „Max Heap”.

Ce este „Heapify”?

„Heapify” este principiul heap-ului care asigură poziția nodului. În Heapify, un heap maxim menține întotdeauna o relație cu părintele și copilul, și acesta este nodul părinte va fi mai mare decât nodurile copil.

De exemplu, dacă se adaugă un nou nod, trebuie să remodelăm grămada. Cu toate acestea, ar putea fi nevoie să schimbăm sau să schimbăm nodurile sau să rearanjam matricea. Acest proces de remodelare a unui morman se numește „heapify”.

Iată un exemplu despre cum funcționează heapify:

Adăugarea unui nou nod și Heapify — Adăugarea unui nou nod și heapify

Iată pașii pentru heapify:

Pas 1) S-a adăugat nodul 65 ca fiul drept al nodului 60.

Pas 2) Verificați dacă nodul adăugat nou este mai mare decât cel părinte.

Pas 3) Deoarece este mai mare decât nodul părinte, am schimbat copilul potrivit cu părintele său.

Cum se construiește Heap

Înainte de a construi grămada sau de a îngrămădi un copac, trebuie să știm cum îl vom depozita. Deoarece grămada este un arbore binar complet, este mai bine să utilizați un mulțime pentru a păstra datele mormanului.

Să presupunem că o matrice conține un total de n elemente. Dacă indicele „i” este un nod părinte, atunci nodul din stânga va fi la index (2i+1), iar nodul din dreapta va fi la index (2i+2). Presupunem că indexul matricei începe de la 0.

Folosind aceasta, haideți să stocăm un heap maxim într-o matrice care urmează:

Reprezentarea bazată pe matrice a heap-ului maxim — Reprezentare bazată pe matrice a heap-ului maxim

Algoritmul heapify menține proprietatea heap. Dacă părintele nu are valoarea extremă (mai mică sau mai mare), aceasta va fi schimbată cu nodul copil cel mai extrem.

Iată pașii pentru a acumula un heap maxim:

Pas 1) Începeți de la nodul frunzei.

Pas 2) Găsiți maximul dintre părinte și copii.

Pas 3) Schimbați nodurile dacă nodul copil are o valoare mai mare decât cel părinte.

Pas 4) Urcă cu un nivel.

Pas 5) Urmați pașii 2,3,4 până ajungem la indicele 0 sau sortăm întregul arbore.

Iată pseudo-codul pentru heapify recursiv (heap maxim):

def heapify():
  input→ array, size, i
  largest = i
  left = 2*i + 1
  right = 2*i + 2
if left<n and array[largest ] < array[left]:
  largest = left
if right<n and array[largest ] < array[right]:
  largest = right
If largest not equals i:
  swap(array[i],array[largest])
  heapify(array,n,largest)

Pseudocod pentru sortarea heap

Iată pseudo-codul pentru algoritmul de sortare heap:

Heapify(numbers as an array, n as integer, i as integer):
  largest = i
  left = 2i+1
  right= 2i+2
if(left<=n) and (numbers[i]<numbers[left])
  largest=left
if(right<=n) and (numbers[i]<numbers[right])
  largest=right
if(largest  != i)
  swap(numbers[i], numbers[largest])
  Heapify(numbers,n,largest)
HeapSort(numbers as an array):
  n= numbers.size()
for i in range n/2 to 1
  Heapify(numbers,n,i)
for i in range n to 2
  Swap numbers[i] with numbers[1]
  Heapify(numbers,i,0)

Exemplu de cod de sortare heap în C++

#include <iostream>
using namespace std;
void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;
}
void heapify(int numbers[], int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && numbers[left] < numbers[largest])
    {
        largest = left;
    }
    if (right < n && numbers[right] < numbers[largest])
    {
        largest = right;
    }
    if (largest != i)
    {
	//uncomment the following line to see details in output
        //cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
        swap(numbers[i], numbers[largest]);
        heapify(numbers, n, largest);
    }
}
void heapSort(int numbers[], int n)
{
    for (int i = n/2 - 1; i >= 0; i--)
    {
        heapify(numbers, n, i);
//uncomment the following line to see details in output
 //cout<<"Heapify:\t";
  //display(numbers,n);
    }
    for (int i = n - 1; i >= 0; i--)
    {
        swap(numbers[0], numbers[i]);
        heapify(numbers, i, 0);
    }
}
int main()
{
    int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    cout<<"Initial Array:\t";
    display(numbers,size);
    heapSort(numbers, size);
    cout<<"Sorted Array (descending order):\t";
    display(numbers, size);
}

ieșire:

Initial Array:  10      5       7       9       4       11      45      17      60
Sorted Array (descending order):  60      45      17      11      10      9       7       5       4

Exemplu de cod de sortare heap în Python

def display(arr):
    for i in range(len(arr)):
    print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
    largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
    largest = left
if right < n and numbers[right] < numbers[largest]:
    largest = right
if largest != i:
    numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
    for i in range(n //2,-1,-1):
        heapify(items, n, i) for i in range(n - 1, -1, -1):
        items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)

ieșire:

Initial List:   10      5       7       9       4       11      45      17      60
After HeapSort: 60      45      17      11      10      9       7       5       4

Analiza complexității în timp și spațiu a sortării heap

Există complexitatea timpului și complexitatea spațiului pe care le putem analiza pentru sortarea grămezilor. Pentru complexitatea timpului avem următoarele cazuri:

Cel mai bun caz
Caz mediu
Cel mai rău caz

Heap-ul este implementat pe un arbore binar complet. Deci, la nivelul de jos al arborelui binar, va exista numărul maxim de noduri. Dacă nivelul inferior are n noduri, atunci nivelul de mai sus va avea n/2 noduri.

În acest exemplu, Nivelul 3 are patru articole, nivelul 2 are două elemente, iar nivelul 1 are un articol. Dacă există un număr total de n articole, înălțimea sau nivelul total va fi Log₂(n). Deci, inserarea unui singur element ar putea dura un maxim de iterații Log(n).

Când vrem să luăm valoarea maximă din heap, luăm doar nodul rădăcină. Apoi, din nou, rulați heapify. Fiecare heapify ia Log₂(N) timp. Extragerea maximului durează O(1) timp.

Cea mai bună complexitate a timpului de caz pentru algoritmul de sortare heap

Când toate elementele sunt deja sortate în matrice, va dura O(n) timp pentru a construi heap-ul. Pentru că dacă lista este sortată, atunci inserarea unui element va dura timpul constant care este O(1).

Deci, va dura O(n) timp pentru a crea un max-heap sau min-heap în cel mai bun caz.

Complexitatea medie a timpului de caz pentru algoritmul de sortare heap

Inserarea unui articol sau extragerea unui cost maxim O(log(n)) timp. Deci, complexitatea medie a timpului de caz pentru algoritmul de sortare heap este O(n log(n)).

Complexitatea timpului cel mai rău caz pentru algoritmul de sortare heap

Similar cu cazul mediu, în cel mai rău scenariu, s-ar putea să efectuăm heapify de n ori. Fiecare heapify va costa O(log(n)) timp. Deci, cel mai rău caz de complexitate va fi O(n log(n)).

Complexitatea spațială pentru algoritmul de sortare în grămada

Sortarea grămadă este un algoritm proiectat în loc. Aceasta înseamnă că nu este necesară nicio memorie suplimentară sau temporară pentru a efectua sarcina. Dacă vedem implementarea, vom observa că am folosit swap () pentru a efectua schimbul de noduri. Nu a fost nevoie de altă listă sau matrice. Deci, complexitatea spațiului este O(1).