daily pastebin goal
57%
SHARE
TWEET

ASD Heap

icatalin Jan 17th, 2019 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. class Heap
  4. {
  5.     int v[100];
  6.     int n;//numarul de noduri
  7.     void pushUp(int position);
  8.     void pushDown(int position);
  9. public:
  10.     Heap()
  11.     {
  12.         n = 0;
  13.     }
  14.     Heap(int *v2, int n2);//construieste un heap pe baza vectorului v2
  15.     void insert (int value);//insereaza un element cu valoarea value si ii face pushUP
  16.     void removeHead();//sterge radacina
  17.  
  18.     int getFirst()//returneaza radacina
  19.     {
  20.         if (n != 0)
  21.             return v[1];
  22.     }
  23.  
  24.     int *sort();//sorteaza vectorul aka HeapSort
  25.     void print();
  26. };
  27.  
  28. void swap(int &first, int &second)
  29. {
  30.     int aux = first;
  31.     first = second;
  32.     second = aux;
  33. }
  34.  
  35. Heap::Heap(int *v2, int n2)
  36. {
  37.     for (int i = 1; i <= n2; i++)
  38.         v[i] = v2[i];
  39.  
  40.     for(int i = n/2; i >= 1; i++) //de la primul nod care nu e frunza, apelez pushDown
  41.         pushDown(i);
  42. }
  43.  
  44. void Heap::pushUp(int position)
  45. {
  46.     while (position != 1 && v[position] > v[position / 2])
  47.         swap(v[position], v[position / 2]);
  48.     position = position / 2;
  49. }
  50.  
  51. void Heap::pushDown(int position)
  52. {
  53.     int maximPosition = position;//pozitia fiului cel mai mare
  54.  
  55.     if ( 2 * position <= n && v[position] < v[2 * position])//compar cu fiul stang
  56.         maximPosition = 2 * position;
  57.  
  58.     if (2 * position + 1 <= n && v[2 * position + 1 ] > v[maximPosition])//compar cu fiul drept
  59.         maximPosition = 2 * position + 1;
  60.  
  61.     if (position != maximPosition)
  62.     {
  63.         swap(v[position], v[maximPosition]);
  64.         pushDown(maximPosition);
  65.     }
  66. }
  67.  
  68. void Heap::insert(int value)
  69. {
  70.     n++;
  71.     v[n] = value;
  72.     pushUp(n);
  73. }
  74.  
  75. void Heap::removeHead()
  76. {
  77.     swap(v[1], v[n]);//interschimb radacina cu ultima frunza
  78.     n--;//scad dimensiunea vectorului(arborelui)
  79.     pushDown(1);
  80. }
  81.  
  82. int *Heap::sort()
  83. {
  84.     int nAux = n;
  85.         for (int i = 1; i <= nAux; i++)
  86.         {
  87.             removeHead();
  88.         }
  89.     n = nAux;
  90.     return v;
  91. }
  92.  
  93. void Heap::print()
  94. {
  95.     for (int i = 1; i <= n; i++)
  96.         std::cout<<v[i]<<' ';
  97.     std::cout<<'\n';
  98. }
  99.  
  100. int main()
  101. {
  102.     Heap heap1;
  103.     heap1.insert(90);
  104.     heap1.insert(50);
  105.     heap1.insert(70);
  106.     heap1.insert(40);
  107.     heap1.insert(35);
  108.     heap1.insert(30);
  109.     heap1.insert(60);
  110.     heap1.insert(12);
  111.     heap1.print();
  112.     heap1.sort();
  113.     heap1.print();
  114.     return 0;
  115. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top