Kashub's Code Barn - "heap"

podświetlone jako text (dodał(a) aaaa @ 2011-01-24 22:05:30)

Twoja wyszukiwarka
Podświetl ten kod w:
Ostatnio dodane:
Losowe wpisy:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
#define Minimum 0
#define Maximum 1
 
 
typedef struct Element
{
    int key;
    int poz;
}Element;
 
typedef struct Element* HeapEl;
 
typedef struct Heap
{
    int max_size;
    int size;
    HeapEl* heaps;
}Heap;
 
Heap* kopiec;
 
void init() //funkcja inicjalizujaca
{
    HeapEl* object;
    kopiec = (Heap*) malloc(sizeof(Heap));
    object = (HeapEl*) malloc(sizeof(HeapEl));
    kopiec->size = 0;
    kopiec->max_size = 1;
    kopiec->heaps = object;
}
 
void zamien(int poz1, int poz2) //funkcja zamieniajaca dwa podane elementy
{
  HeapEl temp_entry;
  ((kopiec->heaps)[poz1])->poz = poz2;
  ((kopiec->heaps)[poz2])->poz = poz1;
  temp_entry = (kopiec->heaps)[poz1];
  (kopiec->heaps)[poz1] = (kopiec->heaps)[poz2];
  (kopiec->heaps)[poz2] = temp_entry;
}
 
void porzadek_dodanie_min(int poz) //funkcja, ktora sprawdza porzadek w kopcu (poziomow Min) po dodaniu wezla
{
     int lvl;
     int changed=0;
     int parent = (poz - 1) / 2;              //rodzic dla wskazanego wezla (co drugi poziom) - tylko minimum
     while (poz > 0)
     {
           if ( ((kopiec->heaps)[parent]->key < (kopiec->heaps)[poz]->key) && changed==0 ) //Jesli klucz rodzica jest mniejszy niz przekazany klucz to nastepuje zamiana
           {
                 zamien(poz, parent);                                                   
                 poz = parent;
                 lvl=Maximum;
           }
           changed = 1;
           parent = (((poz - 1) / 2)-1)/2;
           if(lvl==Minimum)     //Jesli wezel znajduje sie na poziomie Minimum
           {
               if ( ((kopiec->heaps)[parent]->key > (kopiec->heaps)[poz]->key) ) //Jesli klucz rodzica jest wiekszy niz klucz elementu
               {
                  zamien(poz, parent); //zamieniamy
                  poz = parent;
                  changed = 1;
                  lvl=Minimum;                     //ustawiamy poziom jako minimum
               }else{poz=0;}
           }else
           {
               if ( ((kopiec->heaps)[parent]->key < (kopiec->heaps)[poz]->key) && parent!=0 ) //jesli rodzic jest mniejszy niz element i rozny od 0
               {
                  zamien(poz, parent);
                  poz = parent;
                  lvl=Maximum;                   //poziom maximum
               }else{poz=0;}
           }
     }       
}
 
void porzadek_dodanie_max(int poz) //funkcja sprawdzajaca porzadek w kopcu (porzadek max)
{
       int changed;
       int lvl;
       changed=0;
           int parent = (poz - 1) / 2;
          while (poz > 0)
          {
              if ( ((kopiec->heaps)[parent]->key > (kopiec->heaps)[poz]->key) && changed==0 )
              {
                 zamien(poz, parent);
                 poz = parent;
                 lvl=Minimum;
              }
              changed = 1;
              parent = (((poz - 1) / 2)-1)/2;
              if(lvl==Minimum)
              {
                  if ( ((kopiec->heaps)[parent]->key > (kopiec->heaps)[poz]->key) )
                   {
                     zamien(poz, parent);
                     poz = parent;
                     changed = 1;
                     lvl=Minimum;
                  }else{poz=0;}
              }else{
                  if ( ((kopiec->heaps)[parent]->key < (kopiec->heaps)[poz]->key) && parent!=0 )
                  {
                     zamien(poz, parent);
                     poz = parent;
                     lvl=Maximum;
                  }else{poz=0;}
              }
          }  
}
 
void porzadek_dodanie(int poz) //Funkcja porzadkujaca kopiec po dodaniu
{
  int lvl;
  lvl = (int)floor(log2(poz+1));
  if (poz >= kopiec->size) //Jesli przeslana poz jest wieksza od rozmiaru - Error
  {
    printf("Blad - przekroczono rozmiar kopca");
    return;
  }
  if((lvl % 2) == Maximum)      //Jesli parzyste to maximum, else minimum
  {
      porzadek_dodanie_max(poz);
  }else
  {
      porzadek_dodanie_min(poz);  
  }
}
//funkcja sprawdzajaca czy na danym poziomie jest mniejsza (wieksza) wartosc
int zamienMinMaxOnLvl(int act_ind, int lvl, int type)
{
  int i,start, stop, num, ind, act;
  act = kopiec->heaps[act_ind]->key;
 
  start = 4*act_ind + 3;
  stop = start + 3;
  ind = start;
  if(start > kopiec->size) return -1;
  num = kopiec->heaps[ind]->key;
  if(type == Maximum)
  {
          if(stop > kopiec->size) stop = kopiec->size;
          for(i=start; i<=stop; i++ )
          {
                       if (kopiec->heaps[i]->key > num) {num = kopiec->heaps[i]->key;ind = i;}
          }
          if(act < num)
          {
                 return ind;    
          }else
          {
                return -1;
          }
  }else{
         if(stop > kopiec->size) stop = kopiec->size;
         for(i=start; i<=stop; i++ ){
                       if (kopiec->heaps[i]->key < num) {num = kopiec->heaps[i]->key;ind = i;}
          }
          if(act > num){
                 return ind;    
          }else{
                return -1;
          }
  } 
}
 
 
 
void porzadek_del_min(int poz)   //funkcja porzadkujaca kopiec po odjeciu min
{
    int maxlvl,lvl,right,left, parent, ctr,tmp, smaller;
    lvl = (int)floor(log2(poz+1)) + 2;                  //obliczenia poziomu na podstawie pozycji
    maxlvl = (int)floor(log2(kopiec->size));
    ctr=1;
  while (ctr>0)
  {
    if(lvl <= maxlvl)
    { 
    tmp = zamienMinMaxOnLvl(poz,lvl, Minimum);
    }
    else{tmp=-1;}
    if(tmp>0)
    {
              zamien(poz, tmp);
              poz=tmp;
              lvl+=2;
    }else
    {
          ctr=-1;
    }
  }
  parent = (poz - 1) / 2;
  left = 2 * poz + 1;
  right = left + 1;
  smaller = right;
 
  if (right > kopiec->size - 1){
      smaller = left;
  }else if (((kopiec->heaps)[left])->key < ((kopiec->heaps)[right])->key){
      smaller = left;
  }
  if ((smaller <= kopiec->size - 1) && (((kopiec->heaps)[smaller])->key < ((kopiec->heaps)[poz])->key) ){
        zamien(poz, smaller);
        poz = smaller;
  }
  if(kopiec->heaps[parent]->key < kopiec->heaps[poz]->key)
  {
        zamien(poz, parent);
  }
}
 
void porzadek_del_max(int poz) //porzadkujemy kopiec po skasowaniu wezla na poziomie max
{
    int maxlvl,lvl,right,left, parent, ctr,tmp, bigger;
    lvl = (int)floor(log2(poz+1)) + 2;
    maxlvl = (int)floor(log2(kopiec->size));
    ctr=1;
  while (ctr>0)
  {
           if(lvl <= maxlvl)
           { 
           tmp = zamienMinMaxOnLvl(poz,lvl, Maximum);}
           else
           {
               tmp=-1;
           }
           if(tmp>0){
              zamien(poz, tmp);
              poz=tmp;
              lvl+=2;
           }else{
          ctr=-1;
          }
  }
  parent = (poz - 1) / 2;
  left = 2 * poz + 1;
  right = left + 1;
  bigger = right;
  if (right > kopiec->size - 1){
      bigger = left;
  }else if (((kopiec->heaps)[left])->key > ((kopiec->heaps)[right])->key){
      bigger = left;
  }
 
    if ((bigger <= kopiec->size - 1) && (((kopiec->heaps)[bigger])->key > ((kopiec->heaps)[poz])->key) ){
        zamien(poz, bigger);
        poz = bigger;
  }
  if(kopiec->heaps[parent]->key > kopiec->heaps[poz]->key)
  {
                                zamien(poz, parent);
  }
}
 
 
int deleteMin()
{
    int tmp;
    if (kopiec->size <= 0)
    {
         return 0;
    }else
    {
        tmp = ((kopiec->heaps)[0])->key;
        (kopiec->size)--;
        zamien(0,kopiec->size);
        porzadek_del_min(0);
        return tmp;
    }
}
 
int deleteMax()
{
    int tmp,ind;
    if (kopiec->size <= 0)
    {
         return 0;
    }else{
        if((kopiec->heaps)[1]->key > (kopiec->heaps)[2]->key)
        {
            ind=1;
        }
        else{
             ind=2;
        }
        tmp = ((kopiec->heaps)[ind])->key;
        (kopiec->size)--;
        zamien(ind,kopiec->size);
        porzadek_del_max(ind);
        return tmp;
    }
 
}
 
void addItem(int key)
{
  HeapEl nowy_element;
  HeapEl* new_ptr_table;
  nowy_element = (HeapEl)malloc(sizeof(Element));
  nowy_element->key = key;                                              //wstawianie nowego elementu
  nowy_element->poz = kopiec->size;                                     //na najnizszym poziomie kopca
  if(kopiec->size == kopiec->max_size)
  {
      (kopiec->max_size)*=2;
      new_ptr_table = (HeapEl *)realloc(kopiec->heaps, (kopiec->max_size)*sizeof(HeapEl));
      kopiec->heaps = new_ptr_table;
  }
  (kopiec->heaps)[kopiec->size] = nowy_element;
 
  (kopiec->size)++;
     porzadek_dodanie(kopiec->size-1); //uporzadkowanie
}
 
void print()
{
 
 if(kopiec->size > 0)
 {
    int i,parent;
 
    for(i=0;i < (kopiec->size);i++)
    {
        parent = (i - 1) / 2;
        printf("Parent: %d ",((kopiec->heaps)[parent])->key);
        printf("Key: %d \n",((kopiec->heaps)[i])->key);
    }
 }
}
 
 
int main(int argc, char** argv)
{
    int liczba,x,y;
    init();
    srand(time(0));
 
   // addItem(5);
   // addItem(10);
   // addItem(3);
   // addItem(1);
   // addItem(2);
 
   int i=0;
 
   while(i<10000)
   {
                liczba = rand()%15000+1;
                if(liczba>0)
                {
                    addItem(liczba); 
                    i++;
                }
                }
    i=0;
    while(1)
    {
      i++;
      x=deleteMax();
      y=deleteMin();
      if(x==0 && y==0) break;
      printf("Wartosc klucza usuwanego (max) (%d): %d \n",i,x);
      printf("Wartosc klucza usuwanego (min) (%d): %d \n",i,y);
    }
 
      system("pause");
   return 1;
 
}
 
| pompy ciepła Wejherowo | | sklep zoologiczny | | Kredyty mieszkaniowe | | Blog o książkach | | Blogi za darmo | | Załóż za darmo bloga | | Kody programów | | Skracacz adresów | | Gnieżdżewo |