SHARE
TWEET

Untitled

a guest Nov 20th, 2019 94 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <ctime>
  3. using namespace std;
  4.  
  5. template <class T>
  6. class DynamicArray {
  7. public:
  8.     int size;
  9.     int elements;
  10.     T* array;
  11.  
  12.     DynamicArray() {
  13.         size = 1;
  14.         elements = 0;
  15.         array = new T[size];
  16.     }
  17.  
  18.     ~DynamicArray() {
  19.  
  20.         delete[]array;
  21.  
  22.     }
  23.  
  24.     void expandArray() {
  25.         size *= 2;
  26.         T* tmpArray = new T[size];
  27.  
  28.         for (int i = 0; i < elements; i++)
  29.         {
  30.             tmpArray[i] = array[i];
  31.         }
  32.  
  33.         delete[] array;
  34.         array = tmpArray;
  35.  
  36.     }
  37.  
  38.     void addElement(T data) {
  39.         if (elements < size) {
  40.             array[elements] = data;
  41.             elements++;
  42.         }
  43.         else {
  44.             expandArray();
  45.             array[elements] = data;
  46.             elements++;
  47.  
  48.         }
  49.     }
  50.  
  51.     T getElement(int index) {
  52.         if (index < size)
  53.             return array[index];
  54.     }
  55.  
  56.     void deleteElement(int index) {
  57.         if (index < size) {
  58.  
  59.             for (int i = index; i < size; i++)
  60.             {
  61.                 array[i] = array[i + 1];
  62.             }
  63.             array[size] = NULL;
  64.             elements--;
  65.  
  66.         }
  67.     }
  68.  
  69.     string toString(int numbersOfString) {
  70.         string str;
  71.         if (numbersOfString < elements) {
  72.             for (int i = 0; i < numbersOfString; i++)
  73.             {
  74.                 str += to_string(array[i]);
  75.             }
  76.  
  77.         }
  78.         return str;
  79.     }
  80.  
  81.     void changeElement(int index, T data) {
  82.         if (index < elements) {
  83.             array[index] = data;
  84.         }
  85.     }
  86.  
  87.     void clear() {
  88.         for (int i = size - 1; i >= 0; i--)
  89.         {
  90.             array[i] = NULL;
  91.         }
  92.         elements = 0;
  93.     }
  94. };
  95.  
  96. template <class T>
  97. class Heap {
  98. public:
  99.     int size;
  100.     DynamicArray<T>* array;
  101.     Heap() {
  102. size = 0;
  103.      array = new DynamicArray<T>();
  104.     }
  105.  
  106.     void add(T data) {
  107.         array->addElement(data);
  108.         int i = size++;
  109.         int j = (i - 1) / 2;
  110.         while (i > 0 && array->getElement(i) > array->getElement(j)) {
  111.             T tmp = array->getElement(j);
  112.             array->changeElement(j, array->getElement(i));
  113.             array->changeElement(i,tmp);
  114.             i = j;
  115.             j = (i - 1) / 2;
  116.         }
  117.     }
  118.     void swap(int i,int j) {
  119.         T tmp = array->getElement(j);
  120.         array->changeElement(j, array->getElement(i));
  121.         array->changeElement(i, tmp);
  122.     }
  123.  
  124.  
  125.     T deleteTop() {
  126.         if (size > 0) {
  127.             if (size == 1) {
  128.                 T element = array->getElement(0);
  129.                 size = 0;
  130.                 array->clear();
  131.                 return element;
  132.             }
  133.             T element = array->getElement(0);
  134.             array->changeElement(0, array->getElement(size - 1));
  135.             array->deleteElement(size - 1);
  136.             size--;
  137.            
  138.             int i = 0;
  139.             int j = i * 2 + 1;
  140.             int k = i * 2 + 2;
  141.             while (array->getElement(i) < array->getElement(j) || array->getElement(i) < array->getElement(k)) {
  142.                
  143.                     if (array->getElement(j) > array->getElement(k)) {
  144.                         swap(i, j);
  145.                         i = j;
  146.                     }
  147.                     else {
  148.                         swap(i, k);
  149.                         i = k;
  150.                     }
  151.                     j = i * 2 + 1;
  152.                     k = i * 2 + 2;
  153.                     if (j > size || k > size) {
  154.                         break;
  155.                     }
  156.                     if (array->getElement(i) > array->getElement(j) || array->getElement(i) > array->getElement(k)) {
  157.                         break;
  158.                     }
  159.                
  160.                
  161.             }
  162.  
  163.  
  164.             return element;
  165.  
  166.         }
  167.     }
  168.  
  169.     void printHeap() {
  170.         for (int i = 0; i < size; i++) {
  171.             cout<< i << " : " << array->getElement(i)  << " ojciec " << (i-1)/2 <<endl;
  172.         }
  173.     }
  174.     void clear() {
  175.         size = 0;
  176.         array->clear();
  177.     }
  178.  
  179. };
  180.  
  181. int main() {
  182.    
  183.     Heap<int>* kopiec = new Heap<int>();
  184.    
  185.     kopiec->add(25);
  186.     kopiec->add(20);
  187.     kopiec->add(15);
  188.     kopiec->add(6);
  189.     kopiec->add(17);
  190.     kopiec->add(7);
  191.     kopiec->add(13);
  192.     kopiec->add(5);
  193.     kopiec->add(1);
  194.     kopiec->add(22);
  195.     int a = kopiec->deleteTop();
  196.     kopiec->printHeap();
  197.     a = kopiec->deleteTop();
  198.     a = kopiec->deleteTop();
  199.     a = kopiec->deleteTop();
  200.     a = kopiec->deleteTop();
  201.     a = kopiec->deleteTop();
  202.     a = kopiec->deleteTop();
  203.  
  204.     a = kopiec->deleteTop();
  205.     a = kopiec->deleteTop();
  206.     a = kopiec->deleteTop();
  207.     kopiec->printHeap();
  208.    
  209.     return 0;
  210.     /*
  211.     const int MAX_ORDER = 2;
  212.     int dane;
  213.     int a;
  214.     for (int o = 1; o <= MAX_ORDER; o++) {
  215.         const int n = pow(10, o);
  216.         clock_t t1 = clock();
  217.         for (int i = 0; i < n; i++) {
  218.             dane = rand();
  219.             kopiec->add(dane);
  220.         }
  221.         clock_t t2 = clock();
  222.         double time = (t2 - t1) / (double)CLOCKS_PER_SEC;
  223.         cout << "czas dodania: ";
  224.         cout << time << endl;
  225.         t1 = clock();
  226.         for (int i = 0; i < n; i++) {
  227.             a = kopiec->deleteTop();
  228.         }
  229.         t2 = clock();
  230.         time = (t2 - t1) / (double)CLOCKS_PER_SEC;
  231.         cout << "czas usuniecia: ";
  232.         cout << time << endl;
  233.    
  234.  
  235.     }
  236.     return 0;
  237.     */
  238. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top