Heap

1. Descrierea algoritmilor Vezi http://www.regisco.ro/seminarii/StructuriDeDate/Fisiere/heapsort.pdf.

2. Exemplu de implementare #include <assert.h> #include <stdlib.h> /* Formule de calcul pentru accesarea elementelor: Parinte(i) = i / 2 Stanga(i) = i * 2 Dreapta(i) = i * 2 + 1 Macrodefinitii pentru acces la elemente translatate din [1,n] in [0,n-1]: */ #define H_PARINTE(i) (((i) - 1) / 2) #define H_STANGA(i) (((i) + 1) * 2 - 1) #define H_DREAPTA(i) (((i) + 1) * 2) /* Definire tipuri de date utilizate */ typedef int TipHeap; // tipul de date al elementelor typedef struct { int DimVector; // dimensiunea maxima a structurii (mem alocata) int DimDate; // numarul de elemente stocate efectiv int DimHeap; // portiunea organizata sub forma de heap TipHeap* Date; // pointer catre locatia de memorare a datelor } Heap; /* Functii */ // Construire heap gol Heap* CreareHeapGol(int dimMaxima); // Construire heap pe baza unui vector existent Heap* CreareHeap(TipHeap* dateHeap, int dimDate, int dimMaxima); // Distrugere heap (eliberare resurse) void DistrugereHeap(Heap* pHeap); // Sorteaza datele din heap void SortareHeap(Heap* pHeap); // Insereaza un element nou void InserareHeap(Heap* pHeap, TipHeap valoare); // Extrage elementul cu valoare maxima TipHeap ExtragereHeap(Heap* pHeap); void Heapify(Heap* pHeap, int i); // Functie interna /* 1. Functii pentru construire / distrugere heap */ /* CreareHeapGol - aloca memorie pentru un heap gol * DimDate = DimHeap = 0 * DimVector = dimMaxima

*/ Heap* CreareHeapGol(int dimMaxima) { Heap* pHeap; pHeap = (Heap*)malloc(sizeof(Heap)); assert(pHeap != NULL); pHeap->DimHeap = 0; pHeap->DimDate = 0; pHeap->DimVector = dimMaxima; pHeap->Date = (TipHeap*)malloc(dimMaxima * sizeof(TipHeap)); assert(pHeap->Date != NULL); return pHeap; } /* CreareHeap - aloca memorie si construieste un heap pe baza datelor primite * DimDate = DimHeap = dimDate * DimVector = dimMaxima */ Heap* CreareHeap(TipHeap* dateHeap, int dimDate, int dimMaxima) { Heap* pHeap; int i; pHeap = CreareHeapGol(dimMaxima); pHeap->DimDate = dimDate; for (i = 0; i < dimDate; i++) pHeap->Date[i] = dateHeap[i]; pHeap->DimHeap = dimDate; for (i = dimDate / 2; i >= 0; i--) Heapify(pHeap, i); return pHeap; } /* DistrugereHeap - elibereaza memoria folosita de heap */ void DistrugereHeap(Heap* pHeap) { free(pHeap->Date); free(pHeap); pHeap = NULL; } /* 2. Sortare heap */ /* SortareHeap - sorteaza datele din heap prin interschimbarea elementelor * Rezultat: * DimHeap = 1 (nu pastreaza structura de heap) * DimDate = DimHeap initial */ void SortareHeap(Heap* pHeap) { int i; TipHeap temp; pHeap->DimDate = pHeap->DimHeap; for (i = pHeap->DimDate - 1; i > 0; i--) { temp = pHeap->Date[0]; // A[1] <-> A[n] pHeap->Date[0] = pHeap->Date[i]; pHeap->Date[i] = temp; pHeap->DimHeap = pHeap->DimHeap - 1; // eliminam A[n] din heap Heapify(pHeap, 0); // reconstituim structura } }

/* 3. Operatii cozi de prioritate */ /* InserareHeap - insereaza un element in heap pastrand structura * - elementul imediat urmator heap-ului (daca exista) este suprascris */ void InserareHeap(Heap* pHeap, TipHeap valoare) { int pozitieInserare; assert(pHeap->DimHeap < pHeap->DimVector); pHeap->DimHeap++; pHeap->DimDate = max(pHeap->DimDate, pHeap->DimHeap); // determinam locul unde trebuie inserat noul element pozInserare = pHeap->DimHeap - 1; while(pozInserare > 0 && pHeap->Date[H_PARINTE(pozInserare)] < valoare) { pHeap->Date[pozInserare] = pHeap->Date[H_PARINTE(pozInserare)]; pozInserare = H_PARINTE(pozInserare); } pHeap->Date[pozInserare] = valoare; } /* ExtragereHeap - extrage elementul cu valoare maxima din heap */ TipHeap ExtragereHeap(Heap* pHeap) { TipHeap maximum; assert(pHeap->DimHeap > 0); maximum = pHeap->Date[0]; pHeap->Date[0] = pHeap->Date[pHeap->DimHeap - 1]; pHeap->DimHeap--; Heapify(pHeap, 0); return maximum; } /* Heapify - funtie interna pentru refacerea structurii de heap * Preconditii: A[STANGA(i)] si A[DREAPTA(i)] sunt heap-uri * Rezultat: A[i] este heap */ void Heapify(Heap* pHeap, int i) { int pozMaxim = i; TipHeap* A = pHeap->Date; TipHeap temp; if (H_STANGA(i) < pHeap->DimHeap && A[H_STANGA(i)] > A[i]) pozMaxim = H_STANGA(i); if (H_DREAPTA(i) < pHeap->DimHeap && A[H_DREAPTA(i)] > A[pozMaxim]) pozMaxim = H_DREAPTA(i); if (pozMaxim != i) { temp = A[pozMaxim]; A[pozMaxim] = A[i]; A[i] = temp; Heapify(pHeap, pozMaxim); } }