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);

       }

}